C/C++ - Complessità e invariante ciclo liste in C

Ho due funzioni che operano su liste in iterazione e ricorsione e vorrei se possibile alcune conferme
ITERAZIONE
int prodotto (node *l1,node *l2)
{
int somma=0;
if((l1==NULL) && (l2==NULL)) return NULL;
while((l1!=NULL) && (l2!=NULL)){
somma=somma+l1->data*l2->data;
l1=l1->next;
l2=l2->next;
}

while((l1!=NULL) && (l2==NULL)){
somma=somma+l1->data;
l1=l1->next;

}

while((l1==NULL) && (l2!=NULL)){
somma=somma+l2->data;
l2=l2->next;

}



return somma;}

per l' invariante è corretto dire che la somma è compresa tra 0 e la somma fino al valore corrente sommato?
La complessità in tempo e spazio è O(n) per entrambi,ma perchè?Perchè al massimo ci sono n elementi?

RICORSIONE
node *somma(node *l1,int pos,int x,int y,int z){
node *p;int s=0;
if (l1==NULL) return NULL;
else if((pos>x) && (pos<y) && (l1->data%z==0)){
p=newnode();
p->data=l1->data;
p->next=somma(l1->next,pos+1,x,y,z);
return p;}
return somma(l1->next,pos+1,x,y,z);
}
vorrei se possibile la stessa conferma per le complessità
Ringrazio in anticipo chiunque voglia rispodermi