I am working on proving the time complexity for the following problem, but believe I am stuck:
$$T(n) = 2T(n/3 + 1) + n$$
I have checked out this link here on time complexity on cs.stackexchange
However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:
$a = 2, b = 3, c = 1$
In this case, I know logb a is .63, which is less than 1, so the complexity is $Θ(n)$. However, I don't know how to prove that.
I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $Θ(n)$, even though I know that's the answer.
Would anyone be able to assist?