---
# System prepended metadata

title: Homework 6 - Komplexitet och Korrekhet

---

# Homework 6 - Komplexitet och Korrekhet

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

## 1 Induktion
![](https://i.imgur.com/pGImUwO.png)

![](https://i.imgur.com/RdMxyax.png)

Avnänd induktion för att bevisa dessa

## 2 Iterativ korrekhet

Bevisa korrekthet för denna iterativa funktion och ange dess tidskomplexitet

```c
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

```c
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/)
