big o - Log and exponent conversion in Big Oh notation

Question

I'm doing some basic Big-oh problems in class and when reading the answer key, I'm having trouble understanding these log conversions that my professor did. I'd appreciate it if someone could write out the steps.

1. We are trying to show that and this is the first step which i dont understand
2. we are showing that and the first step is
3. We are showing and the first step is

Thank you!

Answer 1

So, a logarithm is just the power you need to raise something to in order to get a certain value. Typically in computer science problems, we are raising 2 to some power (which is also called the base of the logarithm).

So, for example, the (base 2) logarithm of 8 is 3, because you need to raise 2 to the 3rd power to get 8.

A consequence of this is that for any number n, n = 2^(log n). Does that make sense? We know that log n is the power that you need to raise 2 to to reach n, so if you actually raise 2 to that power, you should get n.

So, for your first problem, you are starting with the expression n^(sqrt n). But we know that n = 2^(log n) so we are going to substitute this in for the first n, yielding (2^(log n))^(sqrt n), and by the rules of exponents, this means we can just multiply the two exponents together, yielding 2^(sqrt(n)log(n)) which is the first step you were shown.