[ALGORITMO] Conferma equazione ricorrenza

[gabama]

Avendo questa eq.
aT(n/3) + n/4
per quale valore di a si ottiene theta O(log n)
usando teorema master è corretto?
a=3 perche n elevato log in base 3 di 3 = 1
uguale a f(n) e quindi log

per quale valore di a si ottiene theta O(n^4)
direi per a =81 (1 caso)

come faccio per O(n)?

[gabama]

nessuno?

[YuYevon]

Innanzitutto cosa intendi con "theta O(logn)" e simili? Stiamo parlando di notazione theta o big-O? Sono due cose diverse, in particolare la prima implica la seconda ma non viceversa. Secondo il teorema dell'esperto (o master theorem o come lo vuoi chiamare) mi trovo d'accordo sul secondo punto, e cioè

per quale valore di a si ottiene theta O(n^4)
direi per a =81 (1 caso)

ammesso che quel "theta O(n^4)" stia semplicemente per Θ(n^4), mentre per quanto riguarda questo

per quale valore di a si ottiene theta O(log n)
usando teorema master è corretto?
a=3 perche n elevato log in base 3 di 3 = 1
uguale a f(n) e quindi log

a parte che non ho capito proprio cosa hai scritto, a quale caso del teorema ti riferisci?

[gabama]

intanto grazie ,
si,intendevo proprio quello,Θ
nel secondo e terno punto intendo Θ(log n) e Θ(n)
E' corretto il primo?Come faccio il secondo
Grazie ancora

[gabama]

ultima conferma?

[YuYevon]

Se soltanto riuscissi a comprendere...

Originariamente inviato da gabama
nel secondo e terno punto intendo Θ(log n) e Θ(n)

Cosa intendi? Io ti avevo chiesto per la prima domanda, cioè:

Originariamente inviato da gabama
aT(n/3) + n/4
per quale valore di a si ottiene theta O(log n)
usando teorema master è corretto?
a=3 perche n elevato log in base 3 di 3 = 1
uguale a f(n) e quindi log

cosa significa quello che hai scritto e soprattutto a quale punto del teorema ti riferisci per arrivare alla conclusione.

Originariamente inviato da gabama
E' corretto il primo?Come faccio il secondo

Il primo è quello su cui ti sto chiedendo chiarimenti perché non si capisce, il secondo è corretto e te l'ho pure detto... forse intendevi il terzo, che però non penso si possa risolvere col teorema dell'esperto, devi usare necessariamente quello?

[gabama]

nel primo devo trovare per quale valore di a si ottiene O(log n)

nel terzo,si,posso usare anche altro