Testing complexity using time module

Question

I have a doubt regarding time complexity with recursion. Let's say I need to find the largest number in a list using recursion what I came up with is this:

def maxer(s):
    if len(s) == 1:
        return s.pop(0)
    else:
        if s[0]>s[1]:
            s.pop(1)
        else:
            s.pop(0)
        return maxer(s)

Now to test the function with many inputs and find out its time complexity, I called the function as follows:

import time
import matplotlib.pyplot as plt
def timer_v3(fx,n):
    x_axis=[]
    y_axis=[]
    for x in range (1,n):
        z = [x for x in range(x)]
        start=time.time()
        fx(z)
        end=time.time()
        x_axis.append(x)
        y_axis.append(end-start)
    plt.plot(x_axis,y_axis)
    plt.show()

Is there a fundamental flaw in checking complexity like this as a rough estimate? If so, how can we rapidly check the time complexity?

As a rough estimate, I think it's fine. With more complex functions, the execution time could may depend on other factors and may not be as consistent as the graph you're showing here. But a simple O(n^2) function will result in a visibly different graph. — snnguyen
– snnguyen, Commented Feb 4, 2020 at 21:19
@snnguyen It's funny that you say that, because this function is O(n^2). — kaya3
– kaya3, Commented Feb 6, 2020 at 3:00
Totally overlooked pop() of an arbitrary element. You're right, if the implementation checked from the end of the list (or in reverse) the function would be O(n). — snnguyen
– snnguyen, Commented Feb 6, 2020 at 6:25

kaya3 · Accepted Answer · 2020-02-06 03:24:59Z

Assuming s is a list, then your function's time complexity is O(n²). When you pop from the start of the list, the remaining elements have to be shifted left one space to "fill in" the gap; that takes O(n) time, and your function pops from the start of the list O(n) times. So the overall complexity is O(n * n) = O(n²).

Your graph doesn't look like a quadratic function, though, because the definition of O(n²) means that it only has to have quadratic behaviour for n > n₀, where n₀ is an arbitrary number. 1,000 is not a very large number, especially in Python, because running times for smaller inputs are mostly interpreter overhead, and the O(n) pop operation is actually very fast because it's written in C. So it's not only possible, but quite likely that n < 1,000 is too small to observe quadratic behaviour.

The problem is, your function is recursive, so it cannot necessarily be run for large enough inputs to observe quadratic running time. Too-large inputs will overflow the call stack, or use too much memory. So I converted your recursive function into an equivalent iterative function, using a while loop:

def maxer(s):
    while len(s) > 1:
        if s[0] > s[1]:
            s.pop(1)
        else:
            s.pop(0)
    return s.pop(0)

This is strictly faster than the recursive version, but it has the same time complexity. Now we can go much further; I measured the running times up to n = 3,000,000.

This looks a lot like a quadratic function. At this point you might be tempted to say, "ah, @kaya3 has shown me how to do the analysis right, and now I see that the function is O(n²)." But that is still wrong. Measuring the actual running times - i.e. dynamic analysis - still isn't the right way to analyse the time complexity of a function. However large n we test, n₀ could still be bigger, and we'd have no way of knowing.

So if you want to find the time complexity of an algorithm, you have to do it by static analysis, like I did (roughly) in the first paragraph of this answer. You don't save yourself time by doing a dynamic analysis instead; it takes less than a minute to read your code and see that it does an O(n) operation O(n) times, if you have the knowledge. So, it is definitely worth developing that knowledge.

Collectives™ on Stack Overflow

Testing complexity using time module

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related