Esercizio notazione O grande

[*guitar_joker1]

Non riesco a capire questo esercizio...

dimostrare che 1+2+3+n = O(n^2)

spero che sia chiaro quello che ho scritto... per farlo cosa devo fare in partenza?
grazie

[_luca.barletta]

"guitar_joker":Non riesco a capire questo esercizio...

dimostrare che 1+2+3+n = O(n^2)

spero che sia chiaro quello che ho scritto... per farlo cosa devo fare in partenza?
grazie

intendi forse 1+2+3+...+n = O(n^2) ?

[vl4dster]

guitar_joker devi semplicemente notare che $sum_{i=1}^n i = n(n+1)/2$
e poi applicare/usare la definizione del bigO.

[*guitar_joker1]

"luca.barletta":[quote="guitar_joker"]Non riesco a capire questo esercizio...

dimostrare che 1+2+3+n = O(n^2)

spero che sia chiaro quello che ho scritto... per farlo cosa devo fare in partenza?
grazie

intendi forse 1+2+3+...+n = O(n^2) ?[/quote]

si intendevo proprio quello che hai scritto... scusa il mio errore di scrittura...

vl4d non ho capito la formula...

[vl4dster]

$1+2+\cdots+n=2/2 (1+2+\cdots+n) = 1/2 ((1+1) + (2+2) + \cdots + (n+n))=$
riordinando i termini
$=1/2 (1+n) + (2+(n-1)) +\cdots + (2+(n-1)) + (1+n) = (n(n+1))/2$

E' una cosa super-nota, cerca su google "numeri triangolari" o apri
un qualsiasi libro di algoritmi o matematica discreta.

[*guitar_joker1]

"vl4d":$1+2+\cdots+n=2/2 (1+2+\cdots+n) = 1/2 ((1+1) + (2+2) + \cdots + (n+n))=$
riordinando i termini
$=1/2 (1+n) + (2+(n-1)) +\cdots + (2+(n-1)) + (1+n) = (n(n+1))/2$

quindi continuando la formula troverò (n^2 + n)/2 che è O(n^2),
giusto?

mi potete velocemente ricordare la definizione di O grande?

è che la funzione in esame non può essere minore di quella dentro alle parentesi di O grande? (lo so che non è matamaticamente correto dire così...)

grazie

[Mega-X]

$O(n^2)$ è l'insieme delle funzioni che hanno un infinito di ordine maggiore o uguale rispetto a $f(n) = n^2$

[_luca.barletta]

Per una definizione rigorosa puoi guardare qui

[dasalv12]

Scusate l'ot: ma che è la matematica discreta...quella che si fa sempe gli affari suoi?