[C] Invariante e complessità

[gabama]

Sono nuovo sulle liste,come ho già scritto in alcuni post e vorrei ,da qualcuno esperto sapere in questo caso qual' è l' invariante (e perchè) e anche la complessità in tempo.Grazie a chiunque mi darà suggerimenti

#include <stdlib.h>
#include <stdio.h>

typedef struct nod {
        int data;
        struct nod *next;
        struct nod *prev;
} node;

node *newnode(void)
{
   return (node *)malloc(sizeof(node));
}


node *buildlis()
{
int x;
node *lis, *p, *last;
printf("nuovo numero da inserire in lista:\n");
scanf("%d", &x);
if (x<=0)
lis= NULL; /* caso di lista vuota */
else
{
/* inserzione del primo elemento in una lista */
last=newnode();
lis = last;
last->data = x;
last->next = NULL;
printf("nuovo numero da inserire in lista:\n");
scanf("%d", &x);
while (x>0)

{
p=newnode();
p->data = x;
p->next = NULL;
last->next = p;
last = p;
printf("nuovo numero da inserire in lista:\n");
scanf("%d", &x);
}
}
return(lis);
}
/* Stampa degli elementi di una lista */

/* Stampa degli elementi di una lista */
void printlis(node *lis)
{
     node* tmp;

     tmp = lis;
     int somma=0;float media=0;int conteggio=0;

     while (tmp != NULL) {
           printf(">>>> %d\n", tmp->data) && (somma=somma+tmp->data) && (conteggio=conteggio+1) ;
           tmp = tmp->next;

     }
printf("Somma %d\n",somma);

printf("Conteggio %d \n",conteggio);
media=(somma/conteggio);
printf("Media %f",media);
}


void myFree ( node* top )
{
    node* tmp;
    tmp = top;

    while ( top->next != NULL ) {
          tmp = top->next;
          free(top);
          top = tmp;
    }
}

int cerca(int x, node *lis)
{
int z=0;

while (lis != NULL)
{
if (lis->data==x) z=z+1;
printf("\nL' elemento e' %d",lis->data);
lis=lis->next;
}
return z;


}




int main()
{
    node* head;node* head2;node *dispari;
    int n;int m=6;
    printf ("\n-----LISTA A-----\n");
    head = buildlis (  );
    printf ("\n-----STAMPA LISTA A-----\n");
    int a=3;
    printlis(head);
    printf ("\n-----STAMPA LISTA A MODIFICATA-----\n");
    int cercax=0;
    cercax=cerca(3,head);
    printf ("\nz e' %d\n",cercax);
    if (cercax==0) printf ("\nnon c' e'\n");
    else printf ("\n c' e'\n");
    myFree ( head );

    return 0;
}

[Hysoka]

ma l'invariante di cosa? complessità di cosa?
Credo che si possa ragione un po' sulla funzione cerca. L'invariante non lo so proprio, ma come complessità temporale è theta(n), assolutamente lineare.

[gabama]

si,scusate,è proprio sulla funzione cerca che chiedevo