Salve ragazzi!
Devo svolgere un esercizio di algoritmi ma non so bene come procedere.
L'esercizio è il seguente:
Dopo una sequenza arbitraria di n^(2/3) operazioni di UNION(A,B), quanto vale il numero massimo di cambiamenti di padre che può subire un fissato nodo nel caso peggiore?
a) O((logn)^(2/3))
b) O(log n)
c) $\sum_{i=0}^{n^{2/3} }i $
Scegliere una risposta tra le seguenti, facendo molta attenzione su quale argomento è basata l'analisi ammortizzata del processo.
Io so che nel caso peggiore, un nodo può cambiare padre log(n) volte. Ma credo che questo avvenga se si eseguono n-1 Union, che dovrebbero essere il numero di Union che al più possono essere eseguite fino ad ottenere un unico set. La cosa che mi manda in confusione è il numero di operazioni di union fissato ad n^(2/3).
Potete aiutarmi?
Grazie