1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.