Finding time complexity of a specific python algorithm
Question: Hi I need to understand what is the time complexity of the following
algorithm.

    
    
    def complex(n):
        l=[]
        i=1
        while i<n:
            l=list(range(i))
            i*=2
    

I've got to the point where I realized it runs int(log(n,2)) times over the
loop but I'm having hard time incorporating the range(i) into the final
expression. Any help appreciated thank you.


Answer: You've already worked out that it runs `int(log(n, 2))` iterations. (You can
test that very easily by just adding a counter into the loop, and calling it
with, e.g., 1, 2, 4, 8, 16, 32, 64, etc., and seeing that the counter goes up
1 every time `n` doubles.)

Now you want to know how long the inside of the loop takes. Here, you'd need
to know the time complexity of the `range` and `list` functions. I can give
you the answers to those, and in fact you might be able to guess them, but you
can't really _prove_ that unless you start reading the source code to CPython.
So, let's test it with some simple timing:

    
    
    import timeit
    for i in range(20):
        n = 1 << i
        t = timeit.timeit(lambda: list(range(n))
        print('{} takes {}'.format(n, t))
    

If you run this, you'll see that, once you get beyond around 32, doubling `n`
seems to double the time it takes. So, that means `list(range(n))` is O(n),
right?

Let's verify whether that makes sense. I don't know whether you're using
Python 2.x or 3.x, so I'll work it out both ways.

In 2.x: `range(n)` has to calculate `n` integers, and build a list `n` values
long. That seems like it ought to be O(n).

In 3.x: `range(n)` just returns an object that remembers the number `n`. That
ought to be O(1). But then we call `list` on that `range`, which has to
iterate the whole range, calculating all `n` integers, and building a list `n`
values long. So it's still O(n).

Put that back into your loop, and you have O(log n) times through the loop,
each one O(i) complexity. So, the total time is O(1) + O(2) + O(4) + O(…) +
O(n/4) + O(n/2) + O(n), with log(n) steps in the summation. In other words,
it's the sum of a [geometric
sequence](http://www.mathsisfun.com/algebra/sequences-sums-geometric.html).
And now you can solve the problem. (Or, if not, you're stuck on a new part,
which someone can answer for your very simply if you can't figure it out
yourself.)

* * *

You worked out that the sum is `-(1-2**log(n,2))`. That's not quite right,
because you wanted a closed range, not a half-open range, so it should be
`-(1-2**log(n+1,2))`. But that's probably my fault for not explaining it
clearly, and it doesn't matter too much, so let's go with your version first.

`2**log(n, 2)` is obviously `n`. (If you don't understand exponentiation and
logarithms well enough to understand why, you should find a tutorial on the
math, but meanwhile you can test it with a variety of different values of `n`
to convince yourself.)

Meanwhile, `-(1-x)` for any `x` is just `x-1`.

So, the sum is just `n-1`.

If you go back and use the correct `log(n+1, 2)` instead of `log(n, 2)`,
you'll get `2n-1`.

So, is that correct? Let's test with some actual numbers.

If `n = 16`, you get `1+2+4+8+16 = 31 = 2n-1`. If `n = 1024`, you get
`1+2+4+…+256+512+1024 = 2047 = 2n-1`. Any power-of-2 you throw at it, you get
exactly the right answer. For a non-power-of-2, like 1000, you get
`1+2+4+…+256+512+1000 = 2023`, which is not exactly `2n-1`, but it's always
within a factor of 2. (In fact, it's `n + 2**(ceil(log(n, 2)) - 1`, or `n + m
- 1` where `m` is the `n` rounded up to a power of 2.)

Anyway, `n-1`, `2n-1`, `n + 2**(ceil(log(n, 2)) - 1`… those are all `O(n)`.

And you can go back and test this by timing the whole function with different
values of `n` and see that, beyond very small numbers, when you double `n` it
takes about twice as long.

