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.

 

[CellCoree]

Hello, thank you for your question. The log properties for a constant raised to a power are as follows:

1. loga (x^b) = b * loga (x)
2. loga (ab) = loga (a) + loga (b)

In the case of your example, n^(log4 3) and 3^(log4 n) are not equivalent. This is because the base of the log is different in each expression. In the first expression, the base is 4, while in the second expression, the base is 3. This means that the two expressions are not equal.

However, if we rewrite the first expression as 3^(log4 n), then we can use the second log property to simplify it to 3^(log4 n) = 3^(log4 4) * 3^(log4 3) = 3 * 3^(log4 3) = 3^(log4 3+1) = 3^(log4 4) = n^(log4 3).

So, in the end, both expressions are equivalent and your teacher's result is correct. This is because the log properties allow us to manipulate the expressions to make them equivalent, even though the initial expressions may look different.

I hope this helps to clarify the log properties and how they can be used to solve recursion tree problems. Keep up the good work in your studies!