Odhadovanie časovej zložitosti

Máme pripravených niekoľko programov. Tvojou úlohou bude odhadnúť ich časovú zložitosť.

Programy

# Program 1
for i in range(n):
    print(i)

# Program 2
x = 10
y = 20
z = x + y
print(z)

# Program 3
count = 0
for i in range(n):
    for j in range(n):
        count += 1

# Program 4
count = 0
i = 1
while i <= n:
    count += 1
    i *= 2

# Program 5
result = 0
for i in range(n):
    j = 1
    while j < n:
        result += 1
        j *= 2

# Program 6
def fibonacci(num):
    if num <= 1:
        return num
    return fibonacci(num - 1) + fibonacci(num - 2)

fibonacci(n)

# Program 7
pole = [...] # len(pole) = n
print(42 in pole)

# Program 8
total = 0
for i in range(1, n + 1):
    for j in range(0, n, i):
        total += 1

# Program 9
x = 1
for i in range(n):
    x *= 2

for i in range(m):
    x *= 3

Na jedinom riadku vstupu dostaneš číslo programu, ktorého zložitosť chceme odhadnúť.

Na výstup vypíš časovú zložitosť programu v O-notácií, takto:

Nevypisuj v svojom výpise medzery. Ak vypisuješ viacero premenných, vypíš ich v abecednom poradí.