Originariamente inviato da John360
Dimmi se ho capito bene: theta serve solo per dire su quale grandezza ci si deve basare? Cioè se costante o dipendente da qualcosa?
Riguardo la ricorsione in coda, si, io mi riferivo alla jvm ufficiale.
Non capisco, che significa "su quale grandezza ci si deve basare"?

Queste notazioni servono per classificare funzioni matematiche come appartenenti ad un ordine di grandezza piuttosto che ad un altro. Se una funzione f appartiene a Θ(N²) potrà essere qualcosa come N², 2N², 5N²+7N... ma non potrà essere 5N, 2N³, o una funzione costante. Ma ad esempio, tutte queste funzioni che ho elencato sono in O(N³), e come vedi in questo caso non è molto informativo dato che fra una funzione costante e una cubica c'è una bella differenza.

"costante" è una funzione che restituisce sempre lo stesso risultato, indipendentemente dall'input, insomma una funzione in Θ(1). Per esempio una procedura che alloca sempre e solo 3 variabili intere, indipendentemente dai valori in input, ha un'occupazione spaziale costante, e ce l'avrebbe anche se ne allocasse sempre un miliardo.