Show that the complexity classes Θ(log2 n) and Θ(log2 (n 100)) are equivalent.

Question

Show that the complexity classes Θ(log2 n) and Θ(log2 (n
100)) are equivalent.

Answer 1

It looks like you left out an operator between the n and 100 but if it was +, -, *, /, the answer would be the same anyway. log2(n * 100) produces the largest value of all the operators so I'll prove with that.

Θ(log2 (n * 100))
= Θ(log2 (n) + log2(100)) // by rule 1 of logarithms from https://www.chilimath.com/wp-content/uploads/2017/02/rules-of-exponents.gif
= Θ(max(log2 (n), log2(100))) // Because: Θ(x + y) = Θ(max(x, y))
= Θ(log2 (n)) // Because: max(log2(n), log2(100)) = log2(n) as n approaches positive infinity.

I had trouble finding the axioms for the last 2 steps documented anywhere, unfortunately. Hopefully those steps are small enough and justified enough for your proof.

Answer 2

Thank
Yah

Answer 3

Ills can u help me answer dis question