CODEWITHSUNDEEP
time-complexitybig-o
MV912HB
MV912HB

Reputation: 61

Calculate Time Complexity of function

I am thinking about how to correctly calculate time complexity of this function:

def foo(lst):
    jump = 1
    total = 0
    while jump < len(lst):
        for i in range(0, len(lst), jump):
            total += i
        jump = jump * 2
    return total

I assume that it's O(n) where n is length of list.
Our while loop is O(n) and for loop is also O(n), that means that we got 2*O(n) which equals O(n).
Am I right?

Upvotes: 0

Views: 46

Answers (1)

Sahadat Hossain
Sahadat Hossain

Reputation: 4351

Your calculation have mistakes, for nested loop we multiply the complexity of outer loop with the complexity of inner loop to get the full complexity.

If n is the length of list then the while loop runs log(n) time as every time we are using jump = jump * 2

Inner loop is like, n/1 times when jump = 1, and n/2 times when jump is 2, so the complexity of inner loop is like : (n/1) + (n/2) + (n/4) + (n/8) .... till logn times

Hence total time complexity = n(1 + 1/2 + 1/4 + 1/8 +… till logn). The coefficient of n here is negligible, so the complexity is O(n)

Upvotes: 1

Related Questions