What is the complexity of each of these functions?

Question

Simple circular list implemented in C

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

typedef struct s_no{
    float info;
    struct s_no* proximo;
} no_t;

no_t* cria (){
    return NULL;
}

no_t* insere (no_t* l, float v){
    no_t* p = (no_t*) malloc(sizeof(no_t));
    p->info = v;
    if (l == NULL){
        l = p;
        p->proximo = l;             
    }else{
        no_t *aux = l;
        while (aux->proximo != l){
            aux = aux->proximo;
        }
        aux->proximo = p;
        p->proximo = l;
        l = p;      
    }
    return p;
}

void imprime (no_t* l){
    if (l){
        no_t* q = l;
        do{
            printf("%f\n", q->info);
            q = q->proximo;
        }while (q != l);    
    }
}

void libera (no_t* l){
    no_t* q = l;
    while (q->proximo != l){
        no_t* t = q->proximo;
        free(q);
        q = t;
    }   
}

no_t* retira_inicio(no_t* l, float v){
    if (l == NULL)
        return l;
    if (l == l->proximo){
        free(l);
        return NULL;
    }       
    no_t *p = l;

    while (p != l){
        p = p->proximo;
    }

    no_t *aux = l;

    p->proximo = aux->proximo;

    l = aux->proximo;
    free(aux);
    return l;
}

no_t* retira(no_t* l, float v){
    no_t* ant = NULL;
    no_t *p = l;

    if (l == NULL)
        return l;
    if (p->info == v){

        return retira_inicio(l, v);
    }
    ant = p;
    p = p->proximo;
    while ((p != l) && (p->info != v)){
        ant = p;
        p = p->proximo;
    }
    if (p == l)
        return NULL;
    ant->proximo = p->proximo; 
    free(p);
    return l;
}

Answer 1

When it has a loop walking through the elements of a data structure it is already a great clue that it is linear - O(n). Can be linear modified, for example could be O(n / 2) if you just want to pick up the even items (technically this is not quite Big O).

If there is a loop inside another it already goes to quadratic - O(n²), what is not the case.

Of course it is possible to have a loop and the complexity is logarithmic - O(log n), depends on how the progress of the steps behaves.

Or the loop is not applied to the elements, which could leave the constant complexity - O(1), very rare.

I didn’t do an in-depth analysis, and I may have made a mistake, but it looks like they’re all linear. Linked lists often have this complexity in most applicable algorithms (not all).