Search code examples
pythonruntimebig-ocomputer-science

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

Solution

  • 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.