Python measuring Big O notation algorithms execution time

Question

I am trying to make a function to measure the execution time of Big O algorithms.

I have made a list with the names of the functions, and a list of n values, which are to be given to the function. I have also prepared a 2D matrix for the results.

But I get an error when running the code - argument after * must be an iterable, not int

import time

def o1(n):
    return 1+1

def olog(n):
    while n>0:
        1+1
        n//=2
    return n

def on(n):
    while n>0:
        1+1
        n-=1
    return n

nlst=[10**2, 10**3 , 10**4 , 10**5 ]

algorithms=[ o1 , olog, on ]


def measure(nameF, n):
    begin = time.time()
    nameF(*n)
    end = time.time()
    res=round(end-begin,4)
    return res

for a in range( len (algorithms) ):
    for n in range(1 , len (nlst) + 1 ):
        rlst[a][n] = measure( algorithms[a] , nlst[n-1] )

rlst=[["o1",0,0,0,0],
     ["olog",0,0,0,0],
     ["on",0,0,0,0]]

for x in rlst:
    print (x)

Answer 1

Try this

import time

def o1(n):
    return 1+1
def olog(n):
    while n>0:
        1+1
        n//=2
    return n

def on(n):
    while n>0:
        1+1
        n-=1
    return n

nlst=[10**2, 10**3 , 10**4 , 10**5 ]

algorithms=[ o1 , olog, on ]


def measure(nameF, n):
    begin = time.time()
    nameF(n)
    end = time.time()
    res=round(end-begin,4)
    return res

rlst=[["o1",0,0,0,0],
     ["olog",0,0,0,0],
     ["on",0,0,0,0]]

for a in range( len (algorithms) ):
    for n in range(1 , len (nlst) + 1 ):
        rlst[a][n] = measure( algorithms[a] , nlst[n-1] )



for res in rlst:
    print (res)

However it seems like not everything can be measured

['o1', 0.0, 0.0, 0.0, 0.0]
['olog', 0.0, 0.0, 0.0, 0.0]
['on', 0.0, 0.0012, 0.0012, 0.0044]

Answer 2

Replace the argument *n by n. Also, rlst needs to be initialised before it is used, so move the initialisation of rlst to before the for loop that precedes it. The following code works:

import time

def o1(n):
    return 1+1

def olog(n):
    while n>0:
        1+1
        n//=2
    return n

def on(n):
    while n>0:
        1+1
        n-=1
    return n

nlst=[10**2, 10**3 , 10**4 , 10**5 ]

algorithms=[ o1 , olog, on ]


def measure(nameF, n):
    begin = time.time()
    nameF(n)
    end = time.time()
    res=round(end-begin,4)
    return res


rlst=[["o1",0,0,0,0],
     ["olog",0,0,0,0],
     ["on",0,0,0,0]]

for a in range( len (algorithms) ):
    for n in range(1 , len (nlst) + 1 ):
        rlst[a][n] = measure( algorithms[a] , nlst[n-1] )

for x in rlst:
    print (x)

The functions log n and n grow at very different rates, and so it's difficult to get non-zero values in your output for log n and to also execute the linear time function in a reasonable amount of time. To get nonzero values for the log n function, take n = 10^10000 or 10^100000.

You might have to try different ranges of n values for the different functions. For each function, plot the running times to verify that the behaviour is constant, logarithmic or linear, as a function of n. For eg, if n increases by a factor of 10, the running time of the linear function would increase by a factor of 10.