Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g
2. Bf cresce strettamente più velocemente di g
3. Cf è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente
4. Df cresce strettamente più lentamente di g

Qual è la soluzione della ricorrenza T(n) = 2T(n − 1) + O(1)?

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

Una funzione esegue un ciclo di n iterazioni e poi, separatamente, un altro ciclo di n iterazioni. Qual è la sua complessità temporale?

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

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

Qual è il costo ammortizzato dell'incremento di un contatore binario, dato che un incremento può invertire molti bit?

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