Werkblad Algoritmen & complexiteit met antwoorden

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

1. A2 seconden
2. B8 seconden
3. C1 seconde
4. D4 seconden

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

1. AOngeveer n
2. BOngeveer log₂ n
3. COngeveer n²
4. DOngeveer n / 2

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

1. AMergesort
2. BHeapsort
3. CQuicksort
4. DBubblesort

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

Wat is de tijdcomplexiteit van: for i = 1 to n: for j = 1 to i: doe O(1) werk?

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

De ondergrens voor sorteren op basis van vergelijkingen in het slechtste geval is:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Als je beide eindpunten van elke kant in een maximale koppeling neemt, krijg je een knoopoverdekking. Hoe goed is deze overdekking?

1. AHoogstens twee keer zo groot als een minimale knoopoverdekking
2. BAltijd een minimale knoopoverdekking
3. CVan onbekende kwaliteit vergeleken met het optimum
4. DHoogstens log n keer het minimum

Karatsuba-vermenigvuldiging voldoet aan T(n) = 3T(n/2) + O(n). Wat is de oplossing?

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