Vtyjkyuk

I got this from "4.4 The recursion-tree method for solving recurrences" in book "Introduction to Algorithms"

The recurrence that try to use recursion-tree to solve is:
$T(n) = 3T(n/4) + cn^2$

$$Large3^log_4n=e^ln3fracln nln4=e^ln nfracln 3ln4=n^log_43$$

Let $log_4n=yimplies4^y=n$

Now $n^log_43=4^ylog_43=(4^log_43)^y=3^y$

as for if $log_43=z,3=4^z=4^log_43$

Alternatively,

if $3^log_4n=y,log_4y=log_43log_4n$

and if $n^log_43=z,log_4z=log_4nlog_43$

$$implieslog_4y=log_4zimplies y=z$$

Take the log base 3 of both sides. You get $log_4(n) stackrel?= log_4(3) * log_3(n)$

Then, note that $ log_3(n) *log_4(3) = log_4(3^log_3(n)) = log_4(n)$

You have $log_4$ here, so write both numbers as powers of $4$, and we see immediately that
$$
(4^log_43)^log_4n=(4^log_4n)^log_43
$$
Alternatively (or rather equivalently), take $log_4$ of both numbers, and the numbers are clearly seen as equal.

Let, $log_4n=p$, then $n=4^p$ from definition of $log$. Now, $n^log_43=4^plog_43=(4^log_43)^p=3^p=3^log_4n$.

Also you can do like this:

Use , $3=4^log_43$, then $3^log_4n=(4^log_43)^log_4n=(4^log_4n)^log_43=n^log_43$