Part B: Problem $2$: $(50$ Points$)$ This problem investigates the properties of Big O and Big Theta.

$($a$)$ For all $a,$binR,$a>1$ and $b>1,$ show $lo{g}_{b}n=(lo{g}_{a}n).$

$($Hint: Recall the change of base formula is $lo{g}_{b}n=\frac{lo{g}_{x}n}{lo{g}_{x}b})$

$($b$)$ Let $R_1$ be a relation on $\{f$:$N{R}^{+}\},$ where a $fRg$ if $f=O(g).$ Show $R_1$ is reflexive and transitive, but not symmetric.

$($c$)$ Let $R_2$ be a relation on $\{f$:$N{R}^{+}\},$ where a $fRg$ if $f=(g).$ Show $R_2$ is an equivalence relation.

$($d$)$ Describe the $R_2$ equivalence class $n^2.$ What other functions are in this class?

$($e$)$ Describe the $R_2$ equivalence class $n+n.$ What other functions are in this class?

$($f$)$ Describe the $R_2$ equivalence class $lo{g}_{2}n.$ What other functions are in this class? Consider the result from $($a$).$

$($g$)$ How does this way of defining an equivalence relation helpful for understanding the idea of "equals" for algorithmic complexity? For example, technically $2n^2-n(n+1{)}^2,$ but $2n^2-n=((n+1{)}^2).$