Hemtal 2

A) Komplexitet

Läs om Algorithm Analysis i kursboken

1. Ordna följande funktioner efter hur snabbt dom växer:
   nlog(n2), n2, 2, 210, 2n, log(n), n3, n2log(n), sqrt(n)
2. Ett matrisproblem tar tid T(n)=k*n3 att lösa, där n är matrisens storlek. Om n ökar med en faktor tio, kan vi då kompensera det genom att köpa en dator som är tio gånger snabbare?
   
3. Vad innebär det att en algoritm är O(1)?
4. Vad har följande funktion för tidskomplexitet?

    
   def f(n):
       s = 0
       for i in range(n):
           for j in range(i):
               s += 1
       return s
   

   
   

B) Rekursion

Läs om Tornen i Hanoi i kapitlet Recursion i kursboken

1. Vad är den rekursiva tanken?
2. Vad är basfallet?
3. Visa en lösning för tre ringar.
4. Hur många rekursiva anrop görs för tre ringar?
5. Hur många flyttar behövs med 5 ringar?

---

Hemtalet tas med till övning 2 och rättas där! Den som gjort uppgiften ska skriva sitt namn och personnummer överst till höger på alla blad.

Den som rättar ska skriva sitt namn och personnummer längst ner till vänster på första bladet, samt antal poäng.