python之一个循环的时间复杂度

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

这段代码的时间复杂度是多少？
我的想法是: while 循环执行 log(n) 迭代。每次迭代都会创建新列表。
因此，总时间复杂度为:O(log^2(n))。

我说得对吗？

请您参考如下方法:

while 循环迭代 log(n) 次。

foo + ["a"]:通过复制原始列表创建一个新列表。根据Time Complexity - Python Wiki ，复制一个列表需要 O(n)。

时间复杂度 => 1 + 2 + 3 + ... + 日志(n) => (log(n) + 1) * log(n)/2 => O(log²n)

我运行了一个timeit:(CPython 2.7.5 64 位，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') 

结果:

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