Как решить рекурсивную сложность для t (n) = t (n/2) + 2^n методом итерации?

Question

Я пытаюсь найти верхнюю границу и нижнюю границу, что, вероятно, O (2^n)

T (n) = 1 для n <= 4

Я знаю, что общий орган:

T (n) = t (n/2^(i + 1)) + сумма от i = 0 до k 2^(n/2^i)

---

Отсюда я не знаю, как продолжить ..

Answer 1

Есть некоторые проблемы с вашей нотацией. Общий орган должен быть:

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

После этого шага мы позволили i = log(2, n) - 1, чтобы T(n/2^(i+1)) = T(1).

Следовательно, T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

Обратите внимание, что sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) является 2^n + 2^(n/2) + 2^(n/4) + ..., что меньше, чем 2^n + 2^(n-1) + 2^(n-2) + .... Анкет Однако последний материал 2^(n+1) - 1. Анкет Так что первое - это нечто между 2^n а также 2^(n+1). Анкет Следовательно сумма является O(2^n).

затем T(n) = O(2^n).