Part B: Problem $2$: $(50$ Points$)$ This problem investigates the properties of

Big O and Big Theta.

$($a$)$ For all a$,$ b in R$,$ a $>1$ and b $>1,$ show logbn $=($logan$).$

$($Hint: Recall the change of base formula is logbn $=$ logx n

logx b $)$

$($b$)$ Let R$1$ be a relation on $\{$f $$ N $$ R$+\},$ where a f R g 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 f R g 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 $[$log$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 under$-$

standing the idea of $$equals$$ for algorithmic complexity? For example,

technically $2$n$2$ n $/=($n $+1)2,$ but $2$n$2$ n $=(($n $+1)2).$

$3$