These Python functions do not have runtime as expected

Question

(I’m not sure if this question belongs to or the CS forum. I saved it here because it has Python-specific code. If necessary, if necessary, migrate it!) I’m studying algorithms these days, using Python as a selection tool . Today I wanted to plot three options for a simple task: calculate the average prefix for a given sequence (list).

Here are three options:

import timeit seq = [20, 45, 45, 40, 12, 48, 67, 90, 0, 56, 12, 45, 67, 45, 34, 32, 20] # Quadratic running time def quad (S): n = len(S) A = [0] * n for j in range(n): total = 0 for i in range(j+1): total += S[i] A[j] = total / (j+1) return A # Use prev result def prev (S): n = len(S) A = [0] * n for j in range(n): if j == 0: A[j] = S[j] else: A[j] = (A[j-1]*j + S[j]) / (j+1) return A # Use Python sum method def summ (S): n = len(S) A = [0] * n for j in range(n): A[j] = sum(S[0:j+1])/(j+1) return A def plot_func (name): for i in range(0, 1000000, 100000): t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name)) print(i, ',', t.timeit(number=i)) plot_func('quad') plot_func('prev') plot_func('summ') 

So, I collect the running time of three algorithms and build them. My latest data looked like this:

 Input size Quadratic Prev Summ (x100000) 1 4.92E-007 7.78E-007 3.47E-007 2 1.582717351 0.603501161 0.750457885 3 3.205707528 1.176623609 1.508853766 4 4.796092943 1.76059924 2.295842737 5 6.457349465 2.34945291 3.112500982 6 8.057410897 2.947556047 3.882303307 7 9.59740446 3.520847787 4.654968896 8 11.36328988 4.122617632 5.412608518 9 12.776150393 4.703240974 6.181500295 10 14.704703677 5.282404892 6.882074295 

When plotting these numbers lead to:

Now, according to the next tutorial, the quad and summ functions should execute in quadratic time, and prev in linear time. I see that prev significantly faster than quad and somewhat faster than summ , but they all look like linear functions to me! In addition, summ and prev have a frightening little gap.

Can someone explain what happened?

Answer 1

The asymptotic complexity of the algorithm means its dependence on the input length. Here you do not change the input size between runs, you just change the number of times to run each algorithm (as the timeit() parameter):

  for i in range(0, 1000000, 100000): t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name)) print(i, ',', t.timeit(number=i)) 

To get the right comparison, change the length of your sequence between runs.