CODEWITHSUNDEEP
algorithmnumpytime-complexity
bullbo
bullbo

Reputation: 131

Time complexity: theory vs reality

I'm currently doing an assignment that requires us to discuss time complexities of different algorithms.

Specifically sum1 and sum2

def sum1(a):
    """Return the sum of the elements in the list a."""
    n = len(a)
    if n == 0:
        return 0
    if n == 1:
        return a[0]
    return sum1(a[:n/2]) + sum1(a[n/2:])


def sum2(a):
    """Return the sum of the elements in the list a."""
    return _sum(a, 0, len(a)-1)

def _sum(a, i, j):
    """Return the sum of the elements from a[i] to a[j]."""
    if i > j:
        return 0
    if i == j:
        return a[i]
    mid = (i+j)/2
    return _sum(a, i, mid) + _sum(a, mid+1, j)

Using the Master theorem, my best guess for both of theese are

T(n) = 2*T(n/2) which accoring to Wikipedia should equate to O(n) if I haven't made any mistakes in my assumptions, however when I do a benchmark with different arrays of length N with random integers in the range 1 to 100, I get the following result.

enter image description here

I've tried running the benchmark a multiple of times and I get the same result each time. sum2 seems to be twice as fast as sum1 which baffles me since they should make the same amount of operations. (?). My question is, are these algorthim both linear and if so why do their run time vary.

If it does matter, I'm running these tests on Python 2.7.14.

Upvotes: 2

Views: 297

Answers (2)

EvilTak
EvilTak

Reputation: 7579

sum1 looks like O(n) on the surface, but for sum1 T(n) is actually 2T(n/2) + 2*n/2. This is because of the list slicing operations which themselves are O(n). Using the master theorem, the complexity becomes O(n log n) which causes the difference.

Thus, for sum1, the time taken t1 = k1 * n log n. For sum2, time taken t2 = k2 * n.

Since you are plotting a time vs log n graph, let x = log n. Then, 

t1 = k1 * x * 10^x
t2 = k2 * 10^x

With suitable values for k1 and k2, you get a graph very similar to yours. From your data, when x = 6, 0.6 ~ k1 * 6 * 10^6 or k1 ~ 10^(-7) and 0.3 ~ k2 * 10^6 or k2 = 3 * 10^(-7).

Upvotes: 3

StriplingWarrior
StriplingWarrior

Reputation: 156544

Your graph has log10(N) on the x-axis, which means that the right-most data points are for an N value that's ten times the previous ones. And, indeed, they take roughly ten times as long. So that's a linear progression, as you expect.

Upvotes: 0

Related Questions