INDA25PlusPlus

Allmän information, slides och uppgifter

View the Project on GitHub INDA25PlusPlus/info

Uppgift 11 - Komplexitet och Korrekthet

1 Induktion

Använd induktion för att bevisa dessa formler:

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 korrekthet 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);
}

Inlämning

Döp repot till kth-id-complexity. Repot ska vara privat. Godkända inlämningsformat:

Material