Neither for nor while loop run in linear time O(n) in python

Question

I measured the runtimes of a for and a while loop in python and plotted them with matplotlib. To my surprise, the graphs aren't looking that linear, especially the one of the for loop. It also took longer to loop through 600k numbers than it took to loop through 700k.

What did I do wrong or is it just python which does things differently?

import time
import matplotlib.pyplot as plt

time_while=[]
time_for=[]
for i in range(200000, 1000000+1, 100000):
    t1 = time.time()
    n = 0
    while n < i:
        n += 1
    t2 = time.time()
    time_while.append(round(t2-t1,5))

    t1 = time.time()
    for n in range(i):
       n=n
    t2 = time.time()
    time_for.append(round(t2-t1,5))

x=["200k","300k","400k","500k","600k","700k","800k","900k","1Mio",]
plt.plot(x, time_while,label="while")
plt.plot(x, time_for,label="for")
plt.legend()
plt.show()

Answer 1

By making a slight modification to your code, adding a small summation within each loop I prolong the calculation time and the result will be more stable in terms of small fluctuations in available capacity on your cores. With this approach you clearly see the linearity that is expected.

The plot looks like this

You can see the code used below

import time
import matplotlib.pyplot as plt

time_while=[]
time_for=[]
for i in range(200000, 1000000+1, 100000):
    t1 = time.time()
    n = 0
    while n < i:
        sum(k for k in range(10))
        n += 1
    t2 = time.time()
    time_while.append(round(t2-t1,5))

    t1 = time.time()
    for n in range(i):
        sum(k for k in range(10))
        n=n
    t2 = time.time()
    time_for.append(round(t2-t1,5))

x=["200k","300k","400k","500k","600k","700k","800k","900k","1Mio",]
plt.plot(x, time_while,label="while")
plt.plot(x, time_for,label="for")
plt.legend()
plt.show()