CODEWITHSUNDEEP
pythonruntimebig-ocomputer-science
just got here
just got here

Reputation: 31

Big O notation - python function

What is the Big O notation of this function (as a function of n = len(lst)):

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 thought it was O(n*log(n)) but it's not, trying to understand why it's actually O(n)... I'm kinda new in this so if you could also explain how you got to the answer it'll be the best! thanks

Upvotes: 2

Views: 165

Answers (2)

Kelly Bundy
Kelly Bundy

Reputation: 27588

You keep doubling your step: 1, 2, 4, 8, ...

So those ranges range(0, n, step) that you go through have sizes n, n/2, n/4, n/8, ... (well, approximately - rounded to ints).

The sum of those is 2n (approximately). Which is O(n).

If you didn't know that sum yet, yet, it's easy to see: You start with 0. Then n gets you halfway to 2n. Adding n/2 gets you to 1.5n, again halfway to 2n. Adding n/4 gets you to 1.75, again halfway to 2n. And so on. You only get closer and closer to 2n.

Upvotes: 2

mozway
mozway

Reputation: 260490

The function is O(n).

The function makes about 2*n iterations to got into details (but 2*n is n in big O notation).

For each while loop you're jumping to the next power of 2, so for example for n=1000:

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

Then for each subloop, you go through all element, thus effectively doing sum(successive_powers) (in the example 1+2+4+…+512 = 1023).

The sum of the n first powers is roughly the power of the n+1, so here: 2**(log2(n)+1) ~ 2*n.

An easy way to check this is to change the code:

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

foo(list(range(1000)))
# 2000

Upvotes: 0

Related Questions