16

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
  • 21,820
  • 10
  • 28
  • 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.

ferhatelmas
  • 3,818
  • 1
  • 21
  • 25
  • 2
    I updated my question, can you please comment why it's not possible – Igor Barinov Jul 08 '15 at 07:14
  • The Halting Problem means you can't write a theoretically perfect general program that can always determine the complexity of another program. That doesn't mean you can't write a program that works well enough. Not to mention dynamic O-notation _guessers_ like the one in Google's Benchmark suite (not Python) https://github.com/google/benchmark/blob/main/docs/user_guide.md#calculating-asymptotic-complexity-big-o – The Matt Jul 25 '22 at 00:41
4

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,772
  • 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