Solving Recursion Trees with Log Properties of a Constant

[LauraSuh]

Hi, I'd like to know the log properties when they are the power of a constant. I've searched everywhere but I can't find it. the reason I want to know it is that, when solving a recursion tree problem, my teacher got an result of n^(log4 3) but I got 3^(log4 n). the base of the log haven't changed, but i'd like to know if those are equivalent and if possible, in case the answer is that they are equal, why.
Thx in advance!

 

[Mentallic]

If we have to solve for x in $4^x=3$ then we have defined a log function to answer this problem for us. We denote the answer to this problem as $x=\log_43$. This means that if we plug that expression for x back into the original problem, we get

$$4^{\log_43}=3$$ (1)


Now, for your answer
$$3^{\log_4n}$$ (2)

notice that we can plug the expression I gave in equation (1) into equation (2) to replace the 3. i.e.

$$3^{\log_4n}=\left(4^{\log_43}\right)^{\log_4n}$$

and by exponent properties $(a^b)^c=a^{bc}=a^{cb}=(a^c)^b$ we then have

$$=\left(4^{\log_4n}\right)^{\log_43}$$

But now notice the part in the brackets is equivalent to equation (1), that is, the log base 4 cancels the base of the exponent since they're the same value.

$$4^{\log_4n}=n$$

and so you finally have that your answer is equivalent to

$$n^{\log_43}$$

 

[LauraSuh]

Thank you so much! You're like my super hero right now! =)

 

[Mentallic]

You're welcome By the way, may I ask what the question was? I'm guessing you were finding a time complexity, but I'd just like to see how that order arose.