time complexity for a loop

问题:

foo = []
i = 1
while i < n:
    foo= foo + ["a"]
    i*=2

What is the time complexity of this code?
My thoguht is: the while loop does log(n) iteration. For each iteration new list is created.
So, the total time complexity is: O(log^2(n)).

Am I right?

回答1:

The while loop iterates log(n) times.

foo + ["a"]: Create a new list by copying the original list. According to Time Complexity - Python Wiki, copying a list take O(n).

Time complexity => 1 + 2 + 3 + ... + log(n) => (log(n) + 1) * log(n) / 2 => O(log²n)

---

I ran a timeit: (CPython 2.7.5 64bit, Windows 7)

def f(n):
    foo = []
    i = 1
    while i < n:
        foo = foo + ["a"]
        i *= 2

import timeit
for n in range(20):
    print n, timeit.timeit('f({})'.format(2 ** n), 'from __main__ import f')

Result:

2**0 0.187083903003
2**1 0.455513095565
2**2 0.690063737582
2**3 0.925251130713
2**4 1.16173567555
2**5 1.38232866174
2**6 1.64922777752
2**7 1.89248633685
2**8 2.14087549485
2**9 2.36934465058
2**10 2.62737119511
2**11 2.91843160213
2**12 3.19988987374
2**13 3.43422677799
2**14 3.72119850214
2**15 4.00189195846
2**16 4.31630377356
2**17 4.62789416099
2**18 4.91062905834
2**19 5.24480246883

回答2:

The loop does log(n) iterations.

Now, assuming foo = foo + ["a"] copies immediately each element in footo do the concatenation (as opposed to some fancy list-appending) then for each iteration there are also at most log(n) copies.

So yes, it is log(n)*log(n) = log^2(n)

回答3:

Let’s assume the loop iterates n instead of log(n) times, then the array copy takes 0+1+2+3+4+…+n-2 operations; and with n+2 it takes

0+1+2+3+4+…+n = 1/2·n·(n+1)

operations. For simplicity, let’s replace n+2 by m, so n+2 = m, thus n = m-2, and

1/2·n·(n+1) = 1/2·(m-2)·(m-2+1) = 1/2·(m-2)·(m-1),

which we will use later as

f(m) = 1/2·(m-2)·(m-1).

Now as the loop’s limit is not n+2 but log(n), there are not

f(n+2) = 1/2·((n+2)-2)·((n+2)-1) = 1/2·n·(n+1) (see divergent series above)

but

f(log(n)) = 1/2·(log(n)-2)·(log(n)-1)

operations, which is

1/2·(log²(n)-3·log(n)+2) ∈ Ο(log²(n)). ■