# Homework 6 - Komplexitet och Korrekhet

Lämna in uppgiften som en PDF i ett gitrepo som heter kth-id-complexity

## 1 Induktion


Avnänd induktion för att bevisa dessa

## 2 Iterativ korrekhet

Bevisa korrekthet för denna iterativa funktion med hjälp av loop invarianter och ange dess tidskomplexitet

double expIterative(double x, int n) {
    double res = 1.0;

    for (int i = 0; i < n; i++) {
        res *= x;
    }
    return res;
}

## 3 Rekursiv korrekhet
Bevisa korrekhet för denna rekursiva funktion och ange dess tidskomplexitet

double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterative(x, n);
    }

    return expRecursive(x, n/2) *
           expRecursive(x, (n + 1)/2);
}

Hint: Använd mästarsatsen

## 4 Fixa färdigt saker ni inte känner er färdiga med
Välj en tidigare läxa från en tidigare vecka som ni inte känner er klara med och jobba vidare på den! Lägg lite extra tankar på om ni kan förbättra tids-/minneskomplexiteten på något

## Material
* [Loop invarianter video](https://www.youtube.com/watch?v=vVdDyI1PIUU)
* [Loop invarianter](https://yourbasic.org/algorithms/loop-invariants-explained/)
* [Mästar satsen video](https://www.youtube.com/watch?v=sorlJiiWDRA)
* [Mästar satsen](https://yourbasic.org/algorithms/time-complexity-recursive-functions/)