Ho un dubbio su un esercizio... Mi viene chiesto di calcolare la complessità di questo pseudocodice:
f(A):
n := A.length
i := 1
altre eventuali inizializzazioni eseguite in tempo costante
while i < n
do_something_in_tempo_costante
i := i*2
f(A[1..n/3])
f(A[n/3+1..(2/3)*n])
j := 2
while j < n*n
do_something_in_tempo_costante
j := j*j
return result
La soluzione dice che la complessità è T(N)=2T(n/3)+log(n)+log(log(n)), che poi può essere semplificata con il teorema del maestro...
La semplificazione l'ho capita, ma sinceramente non riesco a capire da dove viene questa soluzione... Immagino che la prima parte (2T(n/3)) venga dal fatto che all'interno del codice abbiamo due ricorsioni (una per il primo terzo, una per il secondo terzo dell'array), quindi la somma è 2T(n/3), correggetemi se sbaglio... Tuttavia non capisco da dove arrivano questi due log(n) nella seconda parte di T(n)!
Grazie in anticipo