Facts:

$1.$ log$($ab$)=$loga$+$logb

$2.$ log$($ac$)=$cloga

$3.$ loga $=$log a logb b

$4.$ blogb a $=$ a Answer the following::

Question $5$

$($a$)$ Using induction and fact $1,$ prove fact $2$ for positive integers c$.$

$($b$)$ Use fact $1$ and fact $2$ to show that log ab $=$ loga$$logb$.$

$($c$)$ It is often said that the bases of logarithms do not matter when finding asymptotic bounds, although this idea is sometimes used too freely. To understand when we can ignore base, use fact $3$ to show that loga n $=\backslash$Theta $($logb n$)$ for any positive a$,$ b$.$

$($d$)$ A common mistake some students make is claiming that clogb n $=\backslash$Theta $($n$).$ Sometimes, they claim this function is exponential. Give a counterexample for both claims $($find a positive c and b in which clogb n is neither exponential in n nor linear in n$).$

$($e$)$ Complete the argument above by showing that for all positive c and b$,$ clogb n $=\backslash$Theta $($nk$)$ for some k $($this implies that such functions are never exponential in n$,$ but the base does matter!$).$ Your argument should use facts $2$ and $4.$