Calcolo di una ricorrenza (Algoritmi)

[Andrew Ryan]

Ho la seguente funzione:

fun1(int k){
      if k<=1 then return;
      fun1(k/9);
      fun1(k/9);
      fun1(k/9);
}

Aiutandomi con quanto mi era stato detto alcuni mesi fa in questo topic -> esercizio-tempo-di-esecuzione-di-funzioni-in-pseudocodice-t98235.html

ho svolto i calcoli in questo modo:

$ c*(n) -> 3*3cT(k/9) -> ... -> 3^(i)cT(k/9^i)$ finchè $k/9^i = 1$ cioè $i =log_9(k)$

$ sum_(i = 0)^(log_9(k)-1)3^(i)c = c*((3^(log_9(k))-1)/(3-1))in O(k^(log_9(3))) = O(k^(1/2)) $

è corretto?

[apatriarca]

Mi sembra corretto, ma gli ultimi passaggi andrebbero secondo me un po' motivati meglio. Non è infatti secondo me a prima vista ovvio che \( 3^{\log_9\,k} = k^{\log_9\,3} \). Si ricava abbastanza velocemente dalle proprietà di logaritmi ed esponenziali, ma ci ho dovuto pensare un attimo prima di decidere che fosse corretta. Ma è possibile che tu faccia un maggiore utilizzo di me dei logaritmi e degli esponenziali e che quella formula sia per te "conosciuta" e ovvia. Ti consiglio però di non seguire troppe scorciatoie quando risolvi gli esercizi che rischi di perdere qualcosa per strada..

[Andrew Ryan]

"apatriarca":Mi sembra corretto, ma gli ultimi passaggi andrebbero secondo me un po' motivati meglio. Non è infatti secondo me a prima vista ovvio che \( 3^{\log_9\,k} = k^{\log_9\,3} \). Si ricava abbastanza velocemente dalle proprietà di logaritmi ed esponenziali, ma ci ho dovuto pensare un attimo prima di decidere che fosse corretta. Ma è possibile che tu faccia un maggiore utilizzo di me dei logaritmi e degli esponenziali e che quella formula sia per te "conosciuta" e ovvia. Ti consiglio però di non seguire troppe scorciatoie quando risolvi gli esercizi che rischi di perdere qualcosa per strada..

ho usato quella formula perchè era stata utilizzata nell'altro topic,altrimenti non avrei cambiato la forma del logaritmo.Comunque gradirei qualche altra conferma perchè non sono troppo pratico in questo tipo di esercizi

[hamming_burst]

"Andrew Ryan":Comunque gradirei qualche altra conferma perchè non sono troppo pratico in questo tipo di esercizi

che altre conferme ti servirebbero?
Con l'albero mi pare hai trovata la complessità. Quando hai dubbi se una complessità è valida o meno, ti ricordo che basta utilizzare l'induzione...