0
$\begingroup$

I'm currently studying recurrence relations, and we had a question where we had to solve the recurrence

$$\ T(n) = nT(n/2)^2 $$

Where $\ T(1) = 6 $

When solving, i came up with the answer

$$\ T(n) = \frac{n^{n-1} 6^n}{2^{n(log_2n - 2)+2}} $$

However, the solution that was given was $$\ T(n) = \frac{6^n4^{n-1}}{n} $$

Curious, i plotted both function on desmos, only to find that they overlap.

Why is this the case? How are these two seemingly different functions giving the same plot, and how is it that we arrive at this other answer?

I have seen a similar question asked here Solve the recurrence relation $T(n) = nT^2(n/2)$ however, what i'm more curious about is why the two graphs come out to be the same.

$\endgroup$
  • $\begingroup$ It's straightforward to simplify yours to obtain the given solution. $\endgroup$ – Matt Samuel Sep 21 at 18:29
  • $\begingroup$ i don't understand how to simplify, could you explain ? $\endgroup$ – Siddhant Mohan Sep 21 at 18:30
  • $\begingroup$ I can't at the moment, but I'm sure someone else will. $\endgroup$ – Matt Samuel Sep 21 at 18:31
  • 1
    $\begingroup$ oof, oh my god i am dumb, i just got it, thanks $\endgroup$ – Siddhant Mohan Sep 21 at 18:32
  • $\begingroup$ yeah 2^(log2) LOL $\endgroup$ – user251865 Sep 21 at 18:32
3
$\begingroup$

Apply the arithmetic rules for powers, exponents and logarithms to find for the denominator $$2^{n(\log_2n - 2)+2}=(2^{\log_2n})^n\cdot 2^{-2n}\cdot 2^2=\frac{4n^n}{4^n}$$


You can also transform the given equation to $$ 4nT(n)=\left(4\frac{n}2T\left(\frac n2\right)\right)^2=...=\left(4\frac{n}{2^k}T\left(\frac n{2^k}\right)\right)^{\large2^k} $$ so that for dyadic powers $n=2^k$ you get $$ 4nT(n)=(4T(1))^n. $$

$\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.