Chapter 4, Problem 41C

Explanation of Solution

Given:

It is given that $lo{g}_{b}f\left(n\right)$ is $\Theta \left(\log f\left(n\right)\right)$.

Big-theta notation:

The function is referred as big-theta only if it is not much worse but also not better than f.

$\Theta \left(f\left(n\right)\right)={\rm O}\left(f\left(n\right)\right)\cap \Omega \left(f\left(n\right)\right)$

Proof:

It is given that the function is $lo{g}_{b}f\left(n\right)$. In this function, use the identity of log that translates $lo{g}_b$ to a logarithm of base 2