Оценить вычислительную сложность алгоритма

Функция hashtab_add:

 void hashtab_add(struct listnode **hashtab, char *key, int value, int mode) 
{ 
    struct listnode *node = malloc(sizeof(struct listnode)); 
    if (node == NULL) 
    { 
        fprintf(stderr, "Failed to allocate memory for list node\n"); 
        exit(EXIT_FAILURE); 
    } 
    unsigned int index = hashtab_hash(key); 
    node->key = strdup(key); 
    node->value = value; 
    node->next = hashtab[index]; 
    hashtab[index] = node; 
}  

Выделение памяти malloc — O(1).
Хеширование ключа hashtab_hash(key) — O(1) (предполагается, что хеш-функция выполняется за константное время).
Копирование ключа strdup(key) — O(len(key)), где len(key) — длина ключа.
Присваивание значений и изменение указателей — O(1).
Таким образом, вычислительная сложность функции hashtab_add в худшем случае зависит от длины ключа и составляет O(len(key)).

Функция hashtab_lookup:

 struct listnode *hashtab_lookup(struct listnode **hashtab, char *key, int mode) 
{ 
    unsigned int index = hashtab_hash(key); 
    struct listnode *node; 
    for (node = hashtab[index]; node != NULL; node = node->next) 
    { 
        if (strcmp(node->key, key) == 0) 
        { 
            return node; 
        } 
    } 
    return NULL; 
}  

Хеширование ключа hashtab_hash(key) — O(1).
Цикл по элементам списка — в худшем случае O(n), где n — количество элементов в списке при данном хеш-индексе.
Сравнение строк strcmp(node->key, key) — O(len(key)), где len(key) — длина ключа.
В худшем случае функция hashtab_lookup должна будет пройти по всем элементам списка в одном бакете, поэтому её сложность составляет O(n * len(key)).

Таким образом, можно сделать вывод, что:

Вычислительная сложность hashtab_add — O(len(key)).
Вычислительная сложность hashtab_lookup — O(n * len(key)), где n — количество элементов в бакете.
Эти оценки предполагают использование хорошей хеш-функции, которая равномерно распределяет элементы по бакетам, чтобы избежать чрезмерного увеличения длины списка в одном бакете.

"Цифры берутся" там из количества повторений фрагмента кода при наихудшем сценарии распределения данных. Если количество повторений не зависит от количества данных, говорят, что сложность О(1). Если есть несколько таких фрагментов, берется наихудший из них.

В твоем случае сложность O(1), поскольку у тебя там поиск по хешу, а он считается мгновенным. Там есть еще цикл поиска коллизий, но если у тебя там все правильно организовано, то количество коллизий по отношению к количеству данных очень малое и ни на что в целом не влияет.