[Algoritmi] Esercizi

[ciccioalex]

salve,
ho dei dubbi riguardo i seguenti esercizi:
Siano A un'array ordinata di n interi e B una min heap su altri n interi. Qual è la complessità del migliore algoritmo possibile che costruisca, date le array, un'array ordinata C di 2n elementi?
O(n)
O(n*lg(n))
O(n*lg^2(n))
O(n^2*lg(n))
Posso dire che O(n) poichè potrei, ad esempio, eseguire il Bucket Sort (supponendo che i numeri siano uniformemente
distribuiti nell'intervallo) in tempo lineare ?

Qual è il numero minimo di confronti per trovare il minimo in un albero binario di ricerca?
a)Teta(1)
b)Teta(lg(n))
c)Teta(n)
d)Teta(n*lg(n))
è la c giusto?

Qual è la profondità minima di una foglia in un albero di decisione per un ordinamento per confronti?
O(1)
O(lg(n))
O(n)
O(n*lg(n))$
E' O(n) (nel caso in cui la risposta ad ogni confronto è Sì)?

[ciccioalex]

Potete aiutarmi anche con il seguente:
Siano A1,A2,A3,A4 quattro array ordinate di n numeri distinti ciascuna. Si supponga di voler fondere le quattro array in un unico array ordinato. Quanti confronti bisogna fare al più (bound più stretto) ?
n
2n
3n
4n