I am trying to prove that the equation:
T(n) = 2T((n/2) +17) + n is O(n log_2(n))
I have to do this by using substitution method, but I am stuck on a step.
I have gotten down to a point where:
T(n) <= 2(c((n/2) +17) * log_2((n/2) +17) ) + n
I am stuck bc I do not know how to simplify the log, or If when doing the substition method, if I was supposed to use ((n/2) + 17) to plug into n.
Help is appreciated.
Alright, so first of all, we need a way of decrementing through the sequence. Let us assume $T(0)$ is the base case.
Then, $T(0) = 2T(17) = 2^2T(\frac{51}{2}) + 2(17) = 2^3T(\frac{119}{4}) + 2(51 + 17) = 2^4T(\frac{255}{8}) + 2(119 + 51 + 17)$
So, we now have a pattern.
$$T(0) = 2^{n+1}T(\frac{17\sum_{k=0}^{n}{2^k}}{2^{n}}) + 34\sum_{m=0}^{n-1}\sum_{k=0}^{m}{2^k} .$$
$$ T(0) = 2^{n+1}T(\frac{17(2^{n+1} - 1)}{2^n}) + 34(-n + 2^{n+1} - 2) $$
Notice, that this isn't making any sense.
That's because your question is nonsensical. You can't define a sequence in terms of later terms, because the recursion will span out to infinity.