Advanced Python: Output Prediction & Time Complexity Quiz

Nested Loop With Early Exit

count = 0
for i in range(n):
    for j in range(n):
        if j > i:
            break
        count += 1

Time Complexity?

Dictionary Lookup Inside Loop

d = {i: i*i for i in range(n)}
for i in range(n):
    x = d[i]

Time Complexity?

List Slicing Trap

lst = list(range(n))
for i in range(n):
    x = lst[:i]

Time Complexity?

List Concatenation

def foo(n):
    result = []
    for i in range(n):
        result = result + [i]
    return result

print(foo(3))

Output & Time Complexity?

Exponential Recursion

def f(n):
    if n <= 1:
        return 1
    return f(n-1) + f(n-1)

print(f(3))

Output & Time Complexity?

List vs Set Membership

lst = list(range(n))
st = set(lst)

for i in range(n):
    if i in lst:
        pass

for i in range(n):
    if i in st:
        pass

Overall Time Complexity?

Halving Loop

i = n
while i > 1:
    i //= 2

Time Complexity?

Recursive + Loop

def bar(n):
    if n == 0:
        return
    for i in range(n):
        print(i)
    bar(n//2)

bar(4)

Output & Time Complexity?

Dictionary Growth

d = {}
for i in range(n):
    d[i] = i
print(len(d))

Output & Time Complexity?

Log Inside Linear Loop

count = 0
i = 1
while i <= n:
    j = 1
    while j <= i:
        count += 1
        j *= 2
    i += 1

Time Complexity?

Generator Consumption

gen = (i*i for i in range(3))
print(list(gen))
print(list(gen))

Output & Time Complexity?

Mutable Default Argument

def add(x, lst=[]):
    lst.append(x)
    return lst

print(add(1))
print(add(2))

Output & Time Complexity?

Nested List Aliasing

arr = [[0]*2]*2
arr[0][0] = 9
print(arr)

Output & Time Complexity?

is vs ==

a = 256
b = 256
c = 257
d = 257
print(a is b, c is d)

Output & Time Complexity?

Chained Comparison

print(1 < 2 < 3 == True)

Output & Time Complexity?

Amortized List Append

lst = []
for i in range(n):
    lst.append(i)

Time Complexity?