Какова будет временная сложность моей функции, которая удаляет элемент из связанного списка?

Question

Учитывая эту структуру:

typedef struct LLNode {
     int info;
     struct LLNode *next;
} LLNode;

и эту рекурсивную функцию, которая удаляет первый узел в связанном списке, переменная-член которого info равна x:

node* deleteNode(LLNode *pHead, int x)
{
     node *ptr;
     
     if (pHead == NULL) {
          return NULL;
     }
     else if (pHead->info == x) {
          *ptr = pHead;
          pHead = pHead->next;
          free(ptr);
     }
     else {
          pHead->next = deleteNode(pHead->next, x);
     }
}

What Я пытаюсь выяснить:

1. Какова будет временная сложность этой функции, учитывая как лучший, так и худший случай?
2. Какой будет временная сложность если бы мы вместо этого удаляли элемент массива?

Мои ответы:

1. Я считаю, что в худшем случае будет пройден весь список, не найдя элемент x, что приведет к O (n). Лучше всего, если бы первый узел в связанном списке содержал x, и функцию не нужно было бы вызывать снова. Будет ли это O (1)?
2. Будет ли временная сложность O (n), так как каждый элемент после найденного элемента в массиве нужно будет переместить?

I правильно? Буду признателен за небольшое руководство, поскольку я все еще новичок в этих концепциях. Любая помощь приветствуется!