Salve a tutti..
mentre mi esercitavo in algoritmi...dopo aver fatto un esercizio sul calcolo del tempo di esecuzione di , appunto , un algoritmo..il testo dice che per semplificare l'analisi,introduciamo uno strumento formale :
ovvero "teta".... per dire ad esempio che:

3n^2 equivale a n^2  o  che 4n + 2 equivale a n  ...

ovvero da cosa si deduce questo???
grazie mille.!

Riesumare discussioni datate è deprecato dal Regolamento, specialmente se rimaste prive di risposte per motivi piuttosto evidenti (si tratta di questioni elementari, ben spiegate in qualsiasi manuale anche di base).

Nel merito, la risposta va comunque corretta. Le notazioni asintotiche ufficiali in analisi algoritmica e complessità computazionale sono normalmente parte delle più generali definizioni di Bachmann–Landau, e comunque si rifanno ai lavori di Donald E. Knuth.
In tale sistema simbolico la complessità o-piccolo (omicron) non coincide affatto con la complessità theta. In particolare, la prima indica che la funzione considerata è asintoticamente dominata da una funzione g(), mentre con la seconda notazione theta indichiamo che la funzione è asintoticamente limitata (sia superiormente, sia inferiormente) dalla g(). Con questo secondo strumento, peraltro spesso ignorato a scapito di un uso piuttosto libero e informale della notazione big-o O(), intendiamo evidenziare in particolare i casi nei quali la differenza prestazionale tra il caso medio e quello peggiore è pressoché nulla.

Peraltro, l'uso della notazione di complessità omicron (che risale alla fine del 1800!) è comune nell'analisi continua, in biologia, in econometria... ma non certo in matematica discreta e teoria della complessità computazionale, stante la sua strettissima parentela con la usuale definizione di limite e la sua applicabilità al campo delle funzioni reali.