Altro esercizio su ricorrenze

[jJjjJ1]

Determinare il tempo di esecuzione $T(n)$ del seguente algoritmo:

algoritmo analizzami( intero n )
       if( n < 10 ) then return n
       else if( n <= 29 ) then return n* analizzami( n-1 )
       else
              x <- n
              j <- x
       while j > 1 do
               x <- x + j 
               j <- j/2
       return analizzami(n/4) * analizzami(n/4)*x

Io ho pensato che:

$T(n) = O(1)$ se $ n < 10$
$T(n) = O(1)$ se $ n <= 30$
$T(n) = T(n/4)*T(n/4) + log_{2} n$ altrimenti

Poiché i primi due casi sono equivalenti li posso considerare come passi base. Tuttavia la ricorrenza non è nella forma del teorema Master. Dunque considero l'albero delle ricorrenze e per facilitare l'analisi considero $ n = 4^k$ con $ k \in N$

L'albero ha altezza $ log_{4} (n) $ e ad ogni livello l'algoritmo costa $O(logn)$ da cui $T(n) = O( log^2 n ) $

Giusto?

[apatriarca]

Mi sembra corretto.