Pagina 1 di 1

Equazione di ricorrenza

MessaggioInviato: 9 set 2017, 11:20
da Patras
Ciao a tutti!
L'ho messo in informatica perché in altri in altri corsi non le ho mai incontrate.
La soluzione offerta non corrisponde con quella mia. La consegna è questa:
Immagine

In sostanza la soluzione è grandina quindi ve la riassumo (tralasciamo il caso costante):
Dimostra che la prima equazione èO(n). Dimostra che la seconda equazione è \Omega(sqrt(n))e la terza ovviamente è \Theta(\log n)

Io concordo con la soluzione a parte l'ultimo punto cioè la stima asintotica complessiva:
Immagine

Cioè T(n)=O(n) e T(n)=\Omega(n)
Ma se c'è il caso del logaritmo (per non dire che c'è anche la radice) come fa a essere \Omega(n)? sarà \Omega(\log n) no?