Allora innanzitutto per quanto riguarda la linearità delle ricorsioni, direi che nessuno di questi algoritmi è ricorsivo lineare visto che tutti hanno più di una chiamata ricorsiva a sé stessi.

Per quanto ne so, non si può parlare in nessun caso (di quelli proposti) nemmeno di "ricorsione di coda" perché questa si ha quando la chiamata ricorsiva è l'ultima istruzione dell'algoritmo.

Per quanto riguarda le complessità di tempo:

TORRI HANOI
...
Complessità in tempo è data dall’ altezza dell’ albero e 2^n-1.
non ho mai lavorato sull'algoritmo delle torri di Hanoi, ma lo conosco teoricamente. In pratica per trovare quella complessità (asinototica) di tempo dovresti risolvere un'equazione di ricorrenza che è la sequente:

T(n) = 0 se n = 0;
T(n) = 2T(n-1) + c se n > 0

dove c è una costante. Comunque dovrebbe essere effettivamente esponenziale, tra l'altro l'algoritmo delle torri di Hanoi se non mi sbaglio va risolto con una tecnica di backtracking che porta sempre a complessità esponenziali. In ogni caso, bisogna risolvere quella ricorrenza e non si può dire così, a impressione.

MERGESORT
...
Complessità in spazio O(log 2 n) ,sostanziale rispetto ai O(n^2)
Complessità in tempo è data dall’ altezza dell’ albero per n.Quindi è O(n*log 2n)
la prima affermazione non l'ho capita proprio...

la seconda è corretta, il Merge Sort ha una complessità di tempo che non degrada mai a quella quadratica.

QUICKSORT
...
Complessità in spazio O(n) ,ma perché?
scusa, in genere come fai a determinare la complessità di spazio? Non vedi forse la dimensione delle strutture dati? Nel caso del Quick Sort non hai semplicemente una lista con n nodi? Quindi perché ti stupisce che sia O(n) ?

Complessità in tempo O(n^2),ma perché?
Il Quick Sort, essenzialmente, è un algoritmo a complessità lin-log ( cioè O(nlogn) ) perché è basato sulla tecnica del divide et impera (come il merge sort). Se fosse a complessità quadratica sarebbe uno dei "peggiori" (alla pari di Insertion Sort, bubble sort e altri), mentre invece al contrario è uno dei migliori (tant'è che in alcuni linguaggi di programmazione esistono delle funzioni di ordinamento che implementano proprio il Quick Sort).

Il fatto che sia O(n^2) dipende da una questione MOLTO sottile, che non è assolutamente trattabile in un topic su un forum... ci sono scienziati che ci hanno scritto interi capitoli sulla complessità del Quick Sort.

Se vuoi qualche idea, ti posso suggerire queste slide:

http://cvprlab.uniparthenope.it/staf...2009/ASD-6.pdf
http://cvprlab.uniparthenope.it/staf...2009/ASD-7.pdf