Tietorakenteet ja algoritmit syksy 2020

Joka kohdassa haluttu vastaus on O(1), O(n), O(n^2) tai O(n^3).

Algoritmi 1

for i = 1 to 5*n
    ...

Aikavaativuus:

Algoritmi 2

for i = 1 to n
    ...
for i = 1 to n
    ...
for i = 1 to n
    ...

Aikavaativuus:

Algoritmi 3

for i = 1 to 2*n
    for j = 1 to n/2
        ...

Aikavaativuus:

Algoritmi 4

for i = 1 to n*n
    ...

Aikavaativuus:

Algoritmi 5

for i = 1 to 100
    for j = 1 to n
        ...

Aikavaativuus:

Algoritmi 6

a = 1
b = n
while a < b
    a++
    b--

Aikavaativuus:

Algoritmi 7

j = 1
for i = 1 to n
    while j < 10*i
        j++

Aikavaativuus:

Algoritmi 8

a = 1
while a < n
    a = n

Aikavaativuus:

The deadline for this task has passed