C - Liste e complessità

[gabama]

So che questa domanda non è direttamente legata alla programmazione,però spero qualcuno mi dia solo questo paio di conferme che ho bisogno,poi il messaggio può tranquillamente essere cancellato se non rientra nelle regole del Forum.Vi ringrazio in anticipo e mi scuso per l' "intrusione"
---ITERAZIONE---

int massimo(node *l1,node *l2)
{int max;
if((l1==NULL) && (l2==NULL)) return 0;
while((l1!=NULL) && (l2!=NULL)){
    if((l1->data+l2->data)>max) max=l1->data+l2->data;
    l1=l1->next;
    l2=l2->next;
  }

while((l1!=NULL) && (l2==NULL)){
    if(l1->data>max) max=l1->data;
    l1=l1->next;

  }

while((l1==NULL) && (l2!=NULL)){
    if(l2->data>max) max=l2->data;
    l2=l2->next;

  }



return max;

}

con questa lista voglio ritornare il valore max,il codice funziona,ma vorrei sapere se l 'invariante è " al generico passo il max è la max somma trovata fino a quel punto"
La complessità in tempo è O(n+m) o semplicemente n dove n è il massimo sumero di nodi tra l1 o l2?
Anche in spazio è così,ma perchè?

---RICORSIONE---

node *alternata(node *l1,node *l2,int pos){
node *p;
if((l1==NULL) && (l2==NULL))  return NULL;
else if((l1!=NULL) && (l2==NULL)){

   p=newnode();
   p->data=l1->data;
   p->next=somma(l1->next,l2,pos+1);
   return p;}



else if((l1==NULL) && (l2!=NULL)){

   p=newnode();
   p->data=l2->data;
   p->next=somma(l1,l2->next,pos+1);
   return p;}




else if((l1!=NULL) && (l2!=NULL)){
   if(pos%2!=0){
   p=newnode();
   p->data=l1->data;
   p->next=somma(l1->next,l2,pos+1);
   return p;}
   else{
   p=newnode();
   p->data=l2->data;
   p->next=somma(l1,l2->next,pos+1);
   return p;}

   }}

Qui duplica i valori presi alternativamente dalle 2 liste
Stessa cosa per il tempo,e in spazio anche O (n) dove n è il massimo numero di record di attivazione contemporaneamente aperti ?

Vi prego ragazzi,è molto importante!