Domande Ricorsioni liste in C

[gabama]

Ragazzi,spero che qualcuno mi possa dare consigli perchè è molto importante
TORRI HANOI

Void nuove(int n,int start,int and,int trip){
	If(n>0){
		Nuove(n-1,start,tmp,and);
	  Alfa   Printf(“%d”->”%d”\n,start,and);
		Nuove(n-1,tmp,and,start)}   beta

Secondo me non è ricorsiva lineare ed è di coda
E’ corretto?
Sono giuste le complessità?

Complessità in spazio O(n) ,perché è proporzionale agli elementi n
Complessità in tempo è data dall’ altezza dell’ albero e 2^n-1.Quindi è dato dal numero di chiamate ricorsive
---------------------
MERGESORT

Typedef struct listnode
{ListEntry entry;
struct listnode * next;
}ListNode;

Typedef struct ListNode
{ListEntry entry;
struct listnode * head;
int count;
}List;

Typedef struct ListEntry
{??,Key;
}ListEntry;

Void mergesort(List *list){
List * secondhalf;   puntatore testa
If ListSize(list)>1
{Divide(list,&secondhalf);
Mergesort(list);
Mergesort(&secondhald);
Mergesort(list,&secondhalf,list);}}

Void divide(List *list,List *secondhalf){
ListNode *current;* midpoint;
If((midpoint=list->head)==head)
Secondhalf->head=NULL;
Else{for(current=midpoint->next;current)
{current=current->next;
If(current){
Midpoint=midpoint->next;
Current=current->next;}}
Secondhalf->head=midpoint->next;
Midpoint->next=null;}}

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)

E’ ricorsiva lineare ?e’ di coda?
--------------------------
QUICKSORT

Void Quicksort(List * list){
Rec Quicksort(list,0,list-count-1);}

Void Rec Quicksort (List * list,int low,int high)
{int pivotpos;
If(low<high)
{pivotpos=partition(list,low,high);
Rec Quicksort(list,low,pivotpos-1);
Rec Quicksort(list,pivotpos+1,high);}}

Complessità in spazio O(n) ,ma perché?
Complessità in tempo O(n^2),ma perché?
E’ ricorsiva lineare ?e’ di coda?