Asymptotic growth of solutions of $T(n)=T(2n/3 +4)+\Theta(n)$

Question

Well, I am having trouble dealing with this:

$$T(n) = T(2n/3 + 4) + \Theta(n)$$

Usually there is a $n - k$ , and not a "$+ k$"

I guessed a solution of $cn$ but the calculation seems off.

Any body seen a problem that looks like this?

Thanks

Answer 1

You can bound T:

$\exists (n_0, p) \in \mathbb{N} \times (0;1)$ such as: $\forall n \lt n_0 \Rightarrow L(n) = L(2n/3) + \Theta(n) \leq T(n) \leq U(n) = U(pn) + \Theta(n)$ (inequalities in terms of 0-notation)

By master theorem (case $c > \log_b a$), $L(n) = U(n) = \Theta(n))$, therefore $T(n) = \Theta(n))$ (computation when $n < n_0$ is $O(1)$ because $n_0$ doesn't depend on $n$).

Answer 2

Assume that $T(n)\leqslant T(2n/3+4)+cn$ for every $n$ and choose $b$ large enough such that $T(n)\leqslant39cn+b$ for every $n\leqslant12$.

Then, for every $n\geqslant13$, $T(n)\leqslant39c\cdot(2n/3+4)+b+cn=27cn+b+12c\cdot13$, which implies $T(n)\leqslant27cn+b+12c\cdot n=39cn+b$.

Thus, the property that $T(n)\leqslant39cn+b$ is hereditary, in particular it holds for every $n$. Since $T(n)\geqslant c'n$, this yields $T(n)=\Theta(n)$.