Werkblad Algoritmen & complexiteit met antwoorden

Wat is de grote O van 3n² + 5n + 2?

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

Wat betekent het als een bewerking in O(1) tijd loopt?

1. AHet verwerkt precies één element per seconde looptijd
2. BHet kan maar één keer worden uitgevoerd
3. CHet duurt altijd precies één seconde
4. DDe looptijd groeit niet met de invoergrootte

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. AConstant
2. BLogaritmisch
3. CLineair
4. DKwadratisch

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

1. AAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet
2. BHet grondtal doet er alleen toe voor kleine n
3. CLogaritmen met verschillende grondtallen verschillen alleen een constante factor
4. DLogaritmen worden altijd afgerond op gehele getallen

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

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

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

1. AO(n log n)
2. BO(dn log k)
3. CO(d(n + k))
4. DO(n²)

Wat moet je doen om aan te tonen dat een nieuw probleem X NP-moeilijk is?

1. AAantonen dat X in polynomiale tijd kan worden geverifieerd
2. BAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer
3. CEen bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X
4. DX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

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