Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

1. AO(n)
2. BO(1)
3. CO(n log n)
4. DO(log n)

Wat is de worst-case tijdcomplexiteit van mergesort?

1. AO(n²)
2. BO(log n)
3. CO(n log n)
4. DO(n)

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

1. AQuicksort
2. BMergesort
3. CBubblesort
4. DInsertion sort

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

1. AZe geeft automatisch 0 terug
2. BZe blijft zichzelf aanroepen totdat de call stack overloopt
3. CDe compiler maakt er altijd een lus van die veilig eindigt
4. DZe loopt in O(1) tijd

Ongeveer hoeveel vergelijkingen heeft binair zoeken in het slechtste geval nodig in een gesorteerde array van 1,000,000 elementen?

1. AOngeveer 20
2. BOngeveer 100
3. COngeveer 1,000
4. DOngeveer 500,000

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

1. AEen array in willekeurige volgorde
2. BEen array waarvan alle elementen verschillend zijn
3. CEen array die al gesorteerd is
4. DEen array van lengte 2

Welke uitspraak over de kleine-o-notatie is juist?

1. An = o(n²), maar n is niet o(n)
2. B2n = o(n), omdat 2n langzaam groeit
3. Cn = o(n), omdat elke functie kleine o van zichzelf is
4. Dn² = o(n)

Het algoritme van Strassen vermenigvuldigt matrices met 7 in plaats van 8 recursieve vermenigvuldigingen van blokken van halve grootte. Wat is de looptijd?

1. AΘ(n³)
2. BΘ(n^{log₂ 7}), ongeveer n^2,81
3. CΘ(n²)
4. DΘ(n² log n)