Big (O) Notation

Question 1

Wat verstaan we onder Worst-case?

Answer 1

Het scenario waarin een algoritme de meeste tijd of ruimte nodig heeft om te voltooien. Dit is het slechtst mogelijke scenario voor het algoritme.

Conclusie: Worst case laat zien hoe het algoritme presteert in de slechtste omstandigheden.

Question 2

Wat verstaan we onder Best-case?

Answer 2

Het scenario waarin een algoritme de minste tijd of ruimte nodig heeft. Dit is het meest gunstige geval voor het algoritme.

Conclusie: Best case toont de prestaties in de best mogelijke situatie.

Question 3

Wat verstaan we onder Average-case?

Answer 3

Dit is de verwachte tijd of ruimte die het algoritme gebruikt, gemiddeld over alle mogelijke inputs. Dit geeft een realistischere maat van de prestaties in typische situaties.

Conclusie: Average case geeft een inzicht in de verwachte prestaties in typische gevallen.

Question 4

Welk algoritme valt onder “Constant time”

Answer 4

Voorbeeld:

Een voorbeeld van een algoritme met
O(1)

O(1)-complexiteit is het ophalen van een element uit een array op basis van een index:

int[] array = {1, 2, 3, 4, 5};
int element = array[2]; // Dit is altijd O(1)

Het maakt niet uit hoe groot de array is, het ophalen van een element via de index kost altijd dezelfde hoeveelheid tijd.

Question 5

Welk algoritme valt onder “Linear time”

Answer 5

Voorbeeld:

Een veelvoorkomend voorbeeld van een lineair tijdscomplex algoritme is het doorlopen van een lijst of array om alle elementen te controleren of te bewerken:

int[] array = {1, 2, 3, 4, 5};
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]); // O(n) omdat je elk element één keer moet doorlopen
}

Als de array 5 elementen bevat, worden er 5 operaties uitgevoerd. Als de array 1000 elementen heeft, worden er 1000 operaties uitgevoerd.

Question 6

Welk algoritme valt onder “Quadratic time”

Answer 6

Voorbeeld:
Een klassiek voorbeeld van een algoritme met
O(n2)

O(n2)-complexiteit is bubble sort, waarbij elk element vergeleken wordt met elk ander element in de lijst:

int[] array = {5, 2, 4, 6, 1, 3};
for (int i = 0; i < array.Length; i++) {
for (int j = 0; j < array.Length; j++) {
if (array[i] < array[j]) {
// verwissel de twee elementen
int temp = array[i];
array[i] = array[j];
array[j] = temp;

Hierdoor wordt voor elke iteratie van de buitenste lus de volledige binnenste lus doorlopen, wat resulteert in een kwadratisch aantal operaties.