Ciao,

guarda se non posti bene il codice (cioè almeno riportandolo tra i tag "code") dubito che in molti avranno voglia di leggerselo, tra l'altro è anche scritto nel regolamento che sarebbe carino rispettare... comunque per adesso stavo dando un'occhiata al primo algoritmo, che riscritto in maniera più guardabile è

codice:
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;
}
e direi che, come dicevi, sia complessità di spazio che di tempo sono O(n), e più precisamente:

la complessità di tempo è O(n) dove n è la lunghezza della lista più lunga (o delle due liste se hanno uguale lungezza). Analiticamente sarebbe T(m, n) = m + n, dove appunto m è la lunghezza della prima lista e n quella della seconda (con eventualmente m = n), ma a livello asintotico questo conta poco e diciamo semplicemente che la complessità di tempo è lineare, ossia O(n);

la complessità di spazio è O(n), dove n è sempre la lunghezza della lista più lunga. Valgono considerazioni molto simili a quelle fatte per la complessità di tempo: dette m e n le lunghezze delle due liste, analiticamente avremmo una complessità di spazio S(m, n) = m + n, ma ancora una volta a livello asintotico ci basta dire che è O(n).

Per quanto riguarda l'invariante di ciclo, anche hai azzeccato... potremmo dire più precisamente che l'invariante sia questa:

"all'i-esima iterazione, la variabile "somma" contiene la somma dei prodotti dei primi i elementi delle due liste".

Per il secondo algoritmo... il consiglio è non solo di postarlo meglio ma anche di specificare cosa fa e cosa sono le variabili pos, x, y e z perché è un po' difficile andare a intuito.