Exercise $9\mathrm{.}8($Logarithmic bound$)$: Show that T$($n$)=$ lg$(1024$ n$)-13$ is $($lg n$)$ by showing that $\_\_$c$1\_\_|$lg n$|<=|$T$($n$)|<=\_\_$c$2\_\_|$lg n$|$ for all n $>\_\_\_.($Please fill in where I left the $"\_\_\_\_\_",$ thnak you$)$

T$($n$)=$ lg$(1024$ n$)-13=$ lg$(\_\_\_\_\_)+$ lg$($n$)-13=$ lg$($n$)-\_\_\_\_\_$

lg$($n$)<=\_\_\_\_\_\_$for n $>0$

$+\_\_\_\_\_\_\_<=0$ for n $>0$

$==================$

So$,$ T$($n$)<=\_\_\_\_\_\_$for n $>0.$ Also, T$($n$)>=0$ for all n $>\_\_\_\_\_\_\_\_$

$($Enter smallest integer for which this is true$)$ so that $|$T$($n$)|=$ T$($n$)$ for all such n$.$ Also, lg$($n$)>=0$ for all n $>\_\_\_\_\_\_($Enter smallest integer for which this is true.$)$ so that $|$lg$($n$)|=$ lg$($n$)$ for all such n$.$ Thus:

$|$T$($n$)|<=\_\_\_\_\_\_|$lg n$|$ for all n $>\_\_\_\_\_($Use the smallest integer in the first blank for which this inequality can be satisfied for all n greater than a certain number. Then in the second blank, substitute either the smallest integer for which it will be true, or the smallest integer that "obviously" results from this proof. Both will be accepted as correct.$)$

So$,$ we showed that T$($n$)$ is Big $\_\_\_\_\_($lg n$)($Fill in the blank with O or Omega$).$

Using the above equality from log laws, we could break up T$($n$)$ into a sum of two terms. Comparing each one individually and then taking the sum, we'd have the following:

lg$($n$)>=\_\_\_\_\_$for n $>0$

$+\_\_\_\_\_\_\_\_>=-1/4$ lg$($n$)$ for n $>\_\_\_\_\_($Enter smallest integer for which this is true.$)$

$==================$

So$,$ T$($n$)>=\_\_\_\_\_\_$for n $>\_\_\_\_\_\_$ and for all such n$,$ we have already shown T$($n$)>=0$ and $|$lg$($n$)|>=0,$ so $|$T$($n$)|>=\_\_\_\_\_\_\_\_|$lg n$|$ for all such n$,$ whereby we have shown T$($n$)$ is Big $\_\_\_\_\_($n lg n$)($Fill in the blank with O or Omega$).$

Combining these results, we have shown that T$($n$)$ is $($lg n$)$ since:

$\_\_\_\_\_|$lg n$|<=|$T$($n$)|<=\_\_\_\_\_|$lg n$|$ for all N $>\_\_\_\_\_\_$ whereby T$($n$)$ is $($nlgn$).$