Analysis of algorithms¶
Part 4 of the course, volume 4 of the lecture notes. The analysis of algorithms: the input size, the running time in the best, worst and average case, and correctness proved with loop invariants.
-
11. Input size
Input size · Asymptotic notation: a recall · Input instance consisting of one natural number · Input instance consisting of two natural numbers · …
-
12. Running time
Running time of an algorithm · Find maximum · Insertion sort · Change of base · …
-
13. Correctness
Correctness of an algorithm · Correctness of Find Maximum · Correctness of Insertion Sort · Correctness of Binary Search · …