Originariamente inviato da John360
ah scusami! Il fatto è che siccome sto studiando java mi viene automatico postare una domanda del genere qui però alcune complessità possono lo stesso variare dato che in java non è permessa la tail recursion! In ogni caso se l'algoritmo occupa delle variabili, perchè la complessità è Θ(1) e non Θ(n) dove n è il numero delle variabili istanziate? E soprattutto perchè hai usato Θ e non O(scusa l'ignoranza )
Infatti ho scritto "generalmente". Comunque non è che Java non supporti la ricorsione in coda, è la piattaforma che non ottimizza questo tipo di ricorsione, o almeno non in generale, forse alcune implementazioni lo fanno. "ricorsione in coda" significa solo che la chiamata ricorsiva è l'ultima operazione fatta dalla procedura, eventualmente ritornandone il valore.

Come fai a dichiarare N variabili dove N è un parametro in input?
Al massimo puoi allocare una quantità di spazio proporzionale a N, per esempio un array di N elementi (ed in questo caso infatti l'array occuperebbe una quantità di spazio in Θ(N)), ovviamente per "variabili" intendevo semplici variabili con un'occupazione costante, non strutture dati.

Θ e O grande sono due notazioni diverse, O grande indica un limite massimo che non viene superato, mentre Θ indica esattamente l'ordine di grandezza. Per esempio, un algoritmo che opera in tempo lineare su N elementi è in O(N), ma è anche in O(N²), in O(N³²)... ma con l'altra notazione puoi solo dire che è in Θ(N). Quest'ultima è sia un limite inferiore sotto il quale non si scende, sia un limite superiore non oltrepassato, specificando quindi l'esatto ordine di grandezza.
Per la cronaca, ci sono anche altre notazioni, trovi le informazioni su Wikipedia. Quando possibile è meglio utilizzare la notazione più informativa.