# two ways of constructing the same list
n = 100
# 1
lst = []
for i in range(n):
lst = lst + [i]
# 2
lst = []
for i in range(n):
lst += [i]
# way 1: less efficient, since a new list is constructed every iteration
# the number of integers written to memory equals 1+2+ ... + n = (n+1)*n/2
# (= asumptotically speaking, grows quadratically with n)
# way 2: more efficient, since the same list is extended again and again
# the number of integers written to memory equals n
# (= asumptotically speaking, grows linearly with n)
# the following code measures the running time of both codes
# for n = (10**4), 2*(10**4)
import time
lst = []
n = (10**4) # 2*(10**4)
start = time.clock()
for i in range(n):
lst += [i]
# lst = lst + [i]
end = time.clock()
print(end-start)
# in accordance with the theory,
# the running time of the inefficient code increases by approximately 2**2 = 4
# as n increases by 2,
# while the running time of the efficient code increases by approximately 2.
# apparently n is large enough for the constants not to play a serious role,
# so that the complexity behavior is similar to the asymptotic behavior.