13

While studying algorithms and data structures I manually evaluate BigO complexity for my script. Is there a way, let say a button in any Python IDE or a package, to calculate BigO for any given function or a program?

UPDATE:

Let's say I have

def print_first_element(a):
    print a[0]

why I can't write the analyzer which will say me ok you access the array (list) by index and its O(1), or

def print_all_element_of_list(a):
    for i in a:
        print i

ok you have full scan so the complexity is O(n)

and so forth

Igor Barinov
  • 16,880
  • 10
  • 27
  • 33
  • In general, there is no such thing that will work with arbitrary code. – David Heffernan Jul 08 '15 at 06:21
  • You can't even tell if a given program and a given input will run in a finite time (look for the halting problem), let alone get a more detailed answer over arbitrary input. – Leeor Jul 08 '15 at 06:27
  • I think you can use a profiler for python for the function and see the run times for different size of inputs..draw the graph in your mind(or a actual graph if you are feeling nerdy) – sethi Jul 08 '15 at 06:29
  • In the first case, `a` could be a dictionary with tree implementation, in which case the function would be O(log n). Or something completely else; we can't really assume it's an instance of the Python's builtin list. – mike3996 Jul 08 '15 at 07:25

2 Answers2

7

Unfortunately, infeasible. See Halting Problem.

ferhat
  • 3,615
  • 1
  • 18
  • 25
1

It's not possible in general. Here's one python program that can compute the complexity for some program: https://github.com/Mortal/complexity

ReyCharles
  • 1,732
  • 10
  • 30
  • Can you please explain why it's not possible? And in case of a space Big-O complexity also – Igor Barinov Jul 08 '15 at 06:24
  • 2
    Well, for one it's impossible to write a program that can decide if another program stops *at all* (see https://en.wikipedia.org/wiki/Halting_problem). Deciding complexity can be reduced to the halting problem: If you can compute a big O of a program then it halts. – ReyCharles Jul 08 '15 at 06:35