Вычислительная сложность программы

Я написал следующую программу, которая должна ответить на этот вопрос

Напишите эффективную функцию для поиска первого неповторенного символа в
строка. Например, первый неповторяющийся символ «итого»
«о» и первый неповторяющийся символ в «качели» это «р». обсуждать
эффективность вашего алгоритма.

Вот что я сделал:

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

class Node
{
public:
Node::Node(char ch)
{
c = ch;
next = NULL;
}
char c;
Node *next;
};

Node* addNode(Node *tail, char ch)
{
if(tail == NULL)
return new Node(ch);
else
{
Node *newN = new Node(ch);
tail->next = newN;
return newN;
}
}

void deleteNode(char ch, Node** head, Node**tail)
{
Node *prev = NULL;
Node *cur = *head;

while(cur!=NULL)
{
if(cur->c == ch)
{
// found cut it
if(prev == NULL)
{
// head cut off
if(*tail == *head)
{
// worst possible, just one element
delete *head;
*head = NULL;
return;
}
else
{
// Head cut off but not just first element
Node *tmp = *head;
*head = (*head)->next;
delete tmp;
return;
}
}
else
{
// delete normal node
if(*tail == cur)
{
// delete tail
Node *tmp = *tail;
*tail = prev;
delete tmp;
return;
}
else
{
// Normal node not tail
prev->next = cur->next;
delete cur;
return;
}
}
}
// no match keep searching
prev = cur;
cur = cur->next;
}
}

int  main()
{
char str[] = "total";
char htable[26];

memset(htable, 0, sizeof(char)*26);

Node *head = NULL;
Node *tail = head;

for(unsigned int i=0;;i++)
{
if(str[i] == '\0')
break;

// check first match
char m = htable[str[i]-'a'];
switch(m)
{
case 0:
{
// first time, add it to linked list
htable[str[i]-'a']++;
tail = addNode(tail, str[i]);
if(head == NULL)
head = tail;
}break;
case 1:
{
// bam, cut it out
htable[str[i]-'a']++;
deleteNode(str[i], &head, &tail);
}break;
}

}

if(head != NULL)
printf("First char without repetition: %c", head->c);
else
printf("No char matched");

return 0;
}

и это работает (хотя я не освободил память в конце программы для связанного списка). Обычно я хэш-таблицу держу с 0, если символ еще не найден, с 1, если он был найден один раз (и он добавлен в связанный список в хвостовой позиции) и 2, если есть хотя бы два вхождения (и должен быть удален связанным списком).

Какова вычислительная сложность этой программы с записью big-O?

Так как этот алгоритм просто проходит один раз для каждого элемента, я думаю, что это O (n), хотя удаление значений в связанном списке (в худшем из возможных случаев) потребовало бы дополнительного O (k ^ 2), где k — длина алфавит используется. Что-то вроде O (n + k ^ 2) — мой выбор, и если строка очень длинная и алфавит ограничен, алгоритм становится очень эффективным.