Fact about logarithms:
log_a x = (log_b x) * (log_a b)
So when you want to change the base of the log from b to a,
you multiply by (log_a b).
Why is this true?
* By definition of log, x = b raised to the power (log_b x)
* Then take the log_a of both sides:
log_a x = log_a (b^{log_b x})
* By rules of logarithms, the righthand side becomes (log_b x) * (log_a b)
* Thus log_a x = (log_b x) * (log_a b)
------
Now for the exercise: Show log_10 (x^2 + 1) = Theta(log_2 x).
(log_10 2) * (log_2 x) = log_10 x by rule above
<= log_10 (x^2 + 1)
= log_2 (x^2 + 1) * (log_10 2) by rule above
<= log_2 (2*x^2) * (log_10 2)
= (1 + 2*log_2 x) * (log_10 2) by rules of logs
<= 3*(log_2 x) * (log_10 2)
= 3(log_10 2) * (log_2 x).
So we can let C_1 = (log_10 x), C_2 = 3(log_10 2), and k = 2.