CODEWITHSUNDEEP
pythonruntimetime-complexity
Omri. B
Omri. B

Reputation: 462

Trouble understanding the runtime complexitiy of a function

I'm currently studying for an exam and the question is as follows; Given function:

def foo(lst):
   count = 0
   while len(lst)>1:
       mid = len(lst)//2
       lst = lst[:mid]
       count += lst[-1]
   return count

What is its runtime complexitiy?

To my understanding, the outer while loop will run logn times due to the list being cut in half each time. Slicing is an O(n) activity, hence, the runtime would be nlogn. Unfortunately, the answers claim the runtime is O(n). Where did I go wrong?

Upvotes: 1

Views: 70

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477035

Short answer: Slicing a list runs in O(n), but since the list is each time cut in half, that means that the n in the second iteration is half of the previous one.

If slicing to k takes exactly k "instructions", then this means that the algorithm comes down to the sum of n/2 + n/4 + n/8 + ... + 1, or more formal:

log n
---     n
\      ---
/        i
---     2
i=1

The above is a geometric serie [wiki] is equal to:

  n/2         n/2
------- - 1 = --- - 1 = n - 1
1 - 1/2       1/2

So the total number of instructions is O(n).

Upvotes: 2

Related Questions