CODEWITHSUNDEEP
pythontimetime-complexity
laklica
laklica

Reputation: 23

Why this strange execution time

I am using this sorting algorithm:

def merge(L,R):
    """Merge 2 sorted lists provided as input
    into a single sorted list
    """
    M = [] #Merged list, initially empty
    indL,indR = 0,0 #start indices
    nL,nR = len(L),len(R)

    #Add one element to M per iteration until an entire sublist
    #has been added
    for i in range(nL+nR):
        if L[indL]<R[indR]:
            M.append(L[indL])
            indL = indL + 1
            if indL>=nL:
                M.extend(R[indR:])
                break
        else:
            M.append(R[indR])
            indR = indR + 1
            if indR>=nR:
                M.extend(L[indL:])
                break
    return M

def func(L_all):

    if len(L_all)==1:
        return L_all[0] 
    else:
        L_all[-1] = merge(L_all[-2],L_all.pop())
        return func(L_all)

merge() is the classical merge algorithm in which, given two lists of sorted numbers, it merges them into a single sorted list, it has a linear complexity. An example of input is L_all = [[1,3],[2,4],[6,7]], a list of N sorted lists. The algorithm applies merge to the last elements of the list until there is just one element in the list, which is sorted. I have evaluated the execution time for different N, using constant length for the lists inside the list and I have obtained an unexpected pattern. The algorithm has a linear complexity but the execution time is constant, as you can see in the graph enter image description here

What could be the explanation of the fact that the execution time does not depend on N?.

Upvotes: 0

Views: 72

Answers (1)

John Coleman
John Coleman

Reputation: 52008

You haven't shown your timing code, but the problem is likely to be that your func mutates the list L_all so that it becomes a list of length 1, containing a single sorted list. After the first call func(L_all) in timeit, all subsequent calls don't change L_all at all. Instead, they just instantly return L_all[0]. Rather than 100000 calls to L_all for each N in timeit , you are in effect just doing one real call for each N. Your timing code just shows that return L_all[0] is O(1), which is hardly surprising.

I would rewrite your code like this:

import functools, random, timeit

def func(L_all):
    return functools.reduce(merge,L_all)

for n in range(1,10):
    L = [sorted([random.randint(1,10) for _ in range(5)]) for _ in range(n)]
    print(timeit.timeit("func(L)",globals=globals()))

Then even for these smallish n you see a clear dependence on n:

0.16632885999999997
1.711736347
3.5761923199999996
6.058960655
8.796722217
15.112843280999996
17.723825805000004
22.803739991999997
26.114925834000005

Upvotes: 1

Related Questions