Big-O notation of 8^log2(n)

Question

I'm confused about what the big-O notation of 8^(log2(n)) would be.

Would you just be able to change it to O(8^n) since the log2 would somewhat act as constant that just reduces the value of n? or would it be something else?

In a somewhat similar case what would be the big-O for log2(n^n). would this just be O(log2(n))?

Answer 1

We'll need the following properties of logs and exponents to understand this one:

1. b^Log_b(x) = x

2. k . Log_b(x) = Log_b(x^k)

3. (x^a)^b = x^a.b

---

For the first problem:

8^Log₂(n)

= (2³)^Log₂(n) (because 8 = 2³)

= 2^{3 . Log₂(n)} (using Prop#3)

= 2^Log₂(n3) (using Prop#2)

= n³ (using Prop#1)

= O(n³)

---

For the second problem:

Log₂(nⁿ)

= n . Log₂(n) (using Prop#2)

= O(n Log(n))