Сложность выяснения временной сложности этой рекурсивной функции

Question

Я думаю, это интересно, но я не уверен в своем решении. Этот алгоритм вычисляет x ⁿ

Если я использую основную теорему, мои рассуждения будут такими:

T(n) = 2 T(n/2) + f(n)

Но f (n) в этом случае равно 1? Потому что n <= 4 является постоянным. Дает мне: </p>

T(n) = Θ(n)

Если я использую замену, я получаю этот ответ

T(n) = Θ(n + log(n))

Я думаю, что я делаю много вещей неправильно. Может ли кто-нибудь указать мне правильное направление?

Answer 1

T (n) = Θ (n + log (n)) - это просто T (n) = Θ (n). Термин низшего порядка (log (n)) может быть опущен при использовании тета.

Кроме того, f (n) равно O (1), потому что вы выполняете только одно умножение (rek (x, n / 2) * rek (x, (n + 1) / 2)) для каждой рекурсии.

Answer 2

Сложность 0 (n). Пояснение: Вы делаете там ВСЕ умножение, как при использовании простого цикла. И у вас нет операции, что числа, разделенные на числа *, больше чем const. Таким образом, сложность составляет около const * 0 (n), что составляет 0 (n).