# use substitution method to prove an equation is in O(n log2 n)

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.

• Is this $T(n) = 2T(\frac{n}{2} + 17) + n$, as in $T(20) = 2T(27) + n$? – retired user Sep 24 '14 at 1:03
• Yes that is the equation. Sorry I did not know how to format everything correctly – mufc Sep 24 '14 at 1:05
• Are you sure? That means you're defining $T(n)$ in terms of $T(m)$ where $m > n$. That's definitely what you mean? – retired user Sep 24 '14 at 1:07
• yeah thats the problem that I am being asked to solve. i know that does not fulfill the m<n – mufc Sep 24 '14 at 1:14
• What a strange question. Alright then. – retired user Sep 24 '14 at 1:15

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.