Question

Show that the function \(f(n)=\left|n^{2} \sin n\right|\) is in neither \(O(n)\) nor \(\Omega(n)\)

Short answer

The function \(f(n)=\left|n^{2} \sin n\right|\) is neither \( O(n) \) nor \( \Omega(n) \). This is due to the fact that the function does not have an upper or lower bound proportional to \( n \).

Step-by-step solution

Find Upper Bound Using Big-O notation

The definition of Big-O notation is \(f(n) = O(g(n))\) if there exist positive constants \(c\) and \(n_{0}\) such that \(0 \leq f(n) \leq c g(n)\) for all \(n \geq n_{0}\). We apply this definition to function \(f(n)=\left|n^{2} \sin n\right|\) and \(g(n) = n\). Setting \( c = 1\) and \(n_{0} = 1\), we have \(0 \leq |n^{2} sin n|\) which is true, but we cannot find a value of \(n\) that satisfies \(|n^{2} \sin n| \leq n\), since the absolute function can achieve values greater than \(n\). Hence, \(f(n)\) is not in \(O(n)\).

Find Lower Bound Using Big-\(\Omega\) notation

The definition of Big-\(\Omega\) notation is \(f(n) = \Omega(g(n))\) if there exist positive constants \(c\) and \(n_{0}\) such that \(0 \leq c g(n) \leq f(n)\) for all \(n \geq n_{0}\). We apply this definition to function \(f(n)=\left|n^{2} \sin n\right|\) and \(g(n) = n\). Choosing \( c = 1\) and \(n_{0} = 1\), we have \(0 \leq n\), which is true, but we cannot find a value of \(n\) that satisfies \(n \leq |n^{2} \sin n|\), since the absolute function can achieve values smaller than \(n\). Therefore, \(f(n)\) is not in \(\Omega(n)\).