Jokaisessa kohdassa aikavaativuudesta sai 1 pisteen ja
tilavaativuudesta sai 1 pisteen. Lyhyet järkevät perustelut
olivat riittävät.

1 (a)

Algoritmin aikavaativuus on O(n), koska algoritmissa on kaksi
peräkkäistä for-silmukkaa, joissa käydään läpi koko taulukko.

Algoritmin tilavaativuus on O(1), koska algoritmissa on
käytössä kiinteä määrä apumuuttujia.


1 (b)

Algoritmin aikavaativuus on O(n), koska algoritmi käy kerran
listan jokaisessa solmussa.

Algoritmin tilavaativuus on O(n), koska algoritmi on toteutettu
rekursiivisesti ja funktiokutsut kasautuvat muistiin.

(Jotkin kääntäjät saattavat optimoida koodin niin,
että viimeisenä esiintyvä rekursiokutsu ei varaa tilaa muistissa,
vaan suoritus palaa funktion alkuun. Näin perusteltuna
myös tilavaativuus O(1) on hyväksyttävä.)


1 (c)

Algoritmin aikavaativuus on O(n^3), koska algoritmissa on kolme
sisäkkäistä for-silmukkaa, joissa käydään läpi koko taulukko.

Algoritmin tilavaativuus on O(1), koska algoritmissa on
käytössä kiinteä määrä apumuuttujia.


1 (d)

Algoritmin aikavaativuus on O(log n), koska funktiolle annettava
parametri puolitetaan, jolloin kutsujen määrä on O(log n).

Algoritmin tilavaativuus on O(log n), koska algoritmi on toteutettu
rekursiivisesti ja funktiokutsut kasautuvat muistiin.