Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Fra83 on 07-04-2011, 10:46:33



Title: Dubbio dimostrazione
Post by: Fra83 on 07-04-2011, 10:46:33
Salve, devo dimostrare che 2n^2=O(n^2). Cioè, dalla definizione di O(g(n)) ho che 2n^2<=cn^2. Quindi dovrebbe venire così:  2n^2<=cn^2--->2n^2/n^2<=c--->  c>=2. E' corretto? Il mio dubbio è se all'inizio bisogna  ignorare la costante di n^2 e quindi procedere diversamente...Grazie a chiunque risponda


Title: Re:Dubbio dimostrazione
Post by: Fra83 on 12-04-2011, 08:02:40
 .quoto


Title: Re:Dubbio dimostrazione
Post by: Daréios89 on 17-04-2011, 16:12:05
Io farei così, ho:

2n^2\leq c n^2

La scrivo al contrario cioè:

cn^2\geq 2n^2

c\geq \frac{2n^2}{n^2}

c\geq 2

Sembra corretta.. .penso

P.S cerchiamo di usare il Latex code.