Как найти высоту дерева рекурсии с добавлением в рекурсивный вызов?

Question

Я пытаюсь найти высоту дерева рекурсии, определенного как

$T(n)=T(\frac{n}{5}+36)+n$

Я понял, что на внутреннем уровне $i$ рекурсивный вызов эквивалентен:

$$\frac{n}{5^i}+\sum_{k=0}^{i-1}{\frac{36}{5^k}}=\frac{n}{5^i}+36\sum_{k=0}^{i-1}{\left(\frac{1}{5}\right)^k}=\frac{n}{5^i} +36\left(\frac{1-\left(\frac{1}{5}\right)^i}{1-\frac{1}{5}}\right)=\frac{n-45}{5^i}+45$$

Примечание: последний шаг - это множество манипуляций с уравнениями, объединенных в один, но я дважды проверил, что он согласуется с Wolfram Alpha.

Но когда я пытаюсь найти высоту дерева $ i $, когда рекурсивный вызов $=1$ выглядит так:

$$\frac{n-45}{5^i}+45=1$$
After some manipulations:
$$5^i=\frac{45-n}{44}$$
$$i=\log_5{\frac{45-n}{44}}$$

Но это значит, что $n$ должно быть $\leq45$, что не имеет никакого смысла!

Где я здесь не так?

Answer 1

Ваше выражение верно:

Но у вас предполагается условие остановки n <= 1.

Может ли это быть достигнуто? Не для n > 45 - при увеличении i член дроби исчезнет, ​​поэтому ввод будет асимптотическим n = 45. Полученное вами условие говорит вам именно это - n может достигнуть 1, только если n < 45, то есть член дроби отрицателен.

Конечно, вы можете исправить это, приняв условие остановки равным n <= C, где C > 45. Глубина тогда: