Time complexity: theory vs reality

Question

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.

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.

As an aside, for your plots: you have the x-axis on logs already, but if you wish to easily observe a suspected linearity, it may help to have the y-axis on logs also. A linear (i.e. `O(n)`) algorithm will then show as a straight line. Log-log plots are the way to go in these cases. — Nelewout, Apr 22 '18 at 10:37

EvilTak · Accepted Answer · 2018-04-21T17:33:25.337

3

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).

edited Apr 21 '18 at 17:33

answered Apr 21 '18 at 16:56

EvilTak

7,091
27
36

I'm no python expert, but [this guy](https://stackoverflow.com/questions/509211/understanding-pythons-slice-notation#comment27984940_509295) says "slicing NumPy arrays returns a view that shares memory with the original." That tells me the slicing operations are `O(1)`. – StriplingWarrior Apr 23 '18 at 15:03
@StriplingWarrior unless I am mistaken, the asker seems to be using built-in Python lists and not numpy arrays. Slicing Python lists causes a copy (an `O(n)` operation), just like the comment you linked specifies. – EvilTak Apr 23 '18 at 17:29
You're probably right. I took the `numpy` tag on the post to mean that's what he was using. I'm definitely out of my element with python, though. – StriplingWarrior Apr 23 '18 at 22:53

score 0 · Answer 2 · answered Apr 21 '18 at 16:12

0

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.

answered Apr 21 '18 at 16:12

StriplingWarrior

151,543
27
246
315

I see, but how come that their runtime differs significantly, don't they do the same amount of operations? – bullbo Apr 21 '18 at 16:21
1

Same order of complexity does *not* mean same time. You can have same order of complexity with wildly different times, if the operations in each case are not equally efficient. – jpp Apr 21 '18 at 16:27
@bullbo: JPP's correct. An algorithm can take 1000x longer than another and still have the same complexity, if it still only takes 1000x longer as you increase `N`. What does your graph look like if you take N. Wouda's advice and make your y-axis logarithmic, and maybe extend it out another x-value or two? – StriplingWarrior Apr 23 '18 at 15:07

Time complexity: theory vs reality

2 Answers2