Dat Do edited beginproblem_a_You_a.tex  about 10 years ago

Commit id: 45f652768b1d9c33500aa660796b65ce348b18ae

deletions | additions      

       

\\  (d) First, we will find the lower bound for $W(n) = 2^{n+1}-n-2$  \\\\  $2^{n+1}-n After removing constants, we find that  \\  $2^{n}-n  \geq 2^n - \frac{2^n}{2}$ which is true for $n > 2$ \\Since $\frac{2^n}{2}$ belongs to $\Omega(2^n)$, $W(n)$ must as well since it is greater than or equal to $\frac{2^n}{2}$  \\\\  Now we will find the upper bound for $W(n) = 2^{n+1}-n-2$  \\\\  Since After removing constants,  \\  $2^{n}-n \leq 2^n$, therefore,  $W(n)$ belongs to $\textit{O}(2^n)$ \\  Since $W(n)$ belongs to both $\Omega(2^n)$ and $\textit{O}(2^n)$,   \\$W(n) = \theta(2^n)$  \\*  \begin{problem}