Временная сложность рекурсивного алгоритма

Question

Как определить временную сложность этого рекурсивного алгоритма?

void func(int n){
    count++;
    if (n == 0) {
    return;
    }
    if (n <= 1000) {
       func(n-1);
       func(n-1);
    } 
    else {
       func(n-1);
       func(n-1);
       func(n-1);
    }
}

Это должно быть довольно просто (это тэта (2 ^ n)?), Но я не уверен и не знаю, как это доказать. Любая помощь будет принята с благодарностью.

Answer 1

Было бы f (n) = O (3 ^ n) (потому что вам нужно учитывать асимптотические границы).

Рассмотрите поиск основной теоремы для более глубокого понимания того, как анализировать время выполнениярекурсивных функций.