Then how about Python's list? What is done exactly when list.append is executed?
For list, is there another larger list initialized and the contents from the old list is copied to it together with the new appended list? "Roel Schroeven" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Ruan schreef: > > My confusion comes from the following piece of code: > > > > memo = {1:1, 2:1} > > def fib_memo(n): > > global memo > > if not n in memo: > > memo[n] = fib_memo(n-1) + fib_memo(n-2) > > return memo[n] > > > > I used to think that the time complexity for this code is O(n) due to its > > use of memoization. > > > > However, I was told recently that in Python, dictionary is a special kind of > > array and to append new element to it or to resize it, it is in fact > > internally inplemented by creating another array and copying the old one to > > it and append a new one. > > That's not correct. Python dictionaries are highly optimized and I > believe the time complexity is amortized constant (i.e. O(1)) for both > insertions and lookups. > > -- > If I have been able to see further, it was only because I stood > on the shoulders of giants. -- Isaac Newton > > Roel Schroeven -- http://mail.python.org/mailman/listinfo/python-list
