|
Malerba
Utente medio
Regione: Puglia
Prov.: Bari
|
 Inserito il - 11/02/2010 : 09:25:03
|
Citazione:
Messaggio inserito da solesat
Come dimostro per induzione la seguente espressione?
n^2 = O(n^2 log n)
Un altro esercizio è il seguente:
Dimostrare la transitività della notazione O. Ossia la veridicità della seguente affermazione: "Se T(n)=O(f(n)) e f(n)=O(g(n)) allora T(n)=O(g(n))"
penso che anche questo esercizio si dimostri per induzione.
Chi mi aiuta???
grazie
Temo che il principio di induzione non sia chiaro, perché con questa dimostrazione non ha nulla a che fare.
Quanto alla prima dimostrazione io non sono capace neanche di capire cosa vorresti dimostrare. Come leggi quella uguaglianza fra n^2 e un ordine di grandezza? Cosa starebbe a significare?
|
Modificato da - Malerba in data 11/02/2010 09:26:41 |
 |
|
Dimostrazione per induzione complessita algoritmi!
Inserito il - 08/02/2010 : 14:32:32
