[Algoritmi] Tempo di esecuzione e ricorrenze

[Riky19931]

Fra qualche giorno ho l'esame di algoritmi e sto avendo qualche problema sulle ricorrenze... Per esempio ho questo algoritmo di cui devo trovare tempo di esecuzione:

test (intero n)
    if n≤81 then return 1
    k = 1
    h = 1
    while k ≤ n do
        for j=1 to k do h++
        k = k+2
    return 9*h + test(n/3)

La relazione di ricorrenza dovrebbe essere questa: \(\displaystyle T(n) = T(n/3) + O(n^2) \)
A questo punto non capisco una cosa, come trovo il caso base? La professoressa scrive questo:

\(\displaystyle T(n) = a \) se \(\displaystyle n ≤ 81 \)
\(\displaystyle T(n) = T(n/3) + bn^2 \) se \(\displaystyle n > 8 \)

Dopo qualche passaggio riesco a risolvere la ricorrenza ottenendo che \(\displaystyle d >= 9/8b \)
Qui ho l'altro problema, lei risolve così:
Prendendo \(\displaystyle d > a \) si ha che \(\displaystyle T(n) = a ≤ dn^2 \) per \(\displaystyle 1≤ n ≤ 81 \), e quindi si potrebbe prendere \(\displaystyle d = a+2b \) e \(\displaystyle n0 = 1 \) e concludere la dimostrazione.

Ma come ha trovato quel d=a+2b e n0=1??

[Riky19931]

Nessuno sa aiutarmi?

[Riky19931]

Ho provato a trovare il tempo di esecuzione di un altro algoritmo:

fun(array A, int i, int f)
    n = f - i + 1;
    t = n^2;
    while t >= 2 do t = t - 2; 
    if (n <= 1) then return 1;
    else return fun(A, i, (i+f)/2) + fun(A, (i+f)/2 + 1, f)

Il while dovrebbe essere eseguito in O(n^2) e poi ci sono 2 chiamate ricorsive su input di lunghezza n/2, dunque la relazione di ricorrenza dovrebbe essere:
\(\displaystyle T(n) = T(n/2) + O(n^2) \)
Sapreste dirmi se è esatto quello che ho scritto???