What is the complexity of each of these functions?

-1

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;
}
    
asked by anonymous 09.04.2016 / 15:52

1 answer

3

When you have a loop walking through the elements of a data structure it is already a big clue that it is linear-O ) .

If you have a loop inside another it already passes to quadratic - O (N2), which is not the case.

Of course it is possible to have a loop and complexity is logarithmic - O (logN).

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

I did not do a deep analysis and I may have been wrong, but it seems like all of them are linear. Linked lists tend to have this complexity in most algorithms.

    
09.04.2016 / 16:27