Я немного запутался в нотации Big-O с рекурсивными функциями

Question

Как найти время выполнения рекурсивной функции. Например:

void fun_list(LLnode_t * head) {
    if (head == NULL) {
        printf("\n");
        return;
    }
    printf("%d ", head-> data);
    if (head->next != NULL) {
        fun_list(head->next);
    }
    printf("%d ", head->data);
} 

Я знаю, что мы должны найти время выполнения рекурсивного случая и базового случая. Я думаю, что время выполнения базового случая O (1). Как мне узнать время выполнения рекурсивного случая?

Answer 1

Сложность по времени будет O (n), где 'n' - это количество вызовов рекурсивных функций. Он в основном рассчитывается путем умножения сложности базового случая на то, сколько раз он вызывается рекурсией. Так что сложность линейная.