# Homework 13 - Komplexitet och Korrekhet

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

## 1 Induktion


Avnänd induktion för att bevisa dessa

## 2 Iterativ korrekhet

Bevisa korrekthet för denna iterativa funktion 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

## 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/)

- [**slides**](https://docs.google.com/presentation/d/1pyO6ooeJvRKA48TOltWsviRkSbNGUa8N0ep0scZTVp0/edit?usp=sharing)