0

Like the title says, I have that type of questions on an assignment. I checked the textbook and read many examples, but those examples are all very straight forward ones where the greatest order of the variable on both side are the same, but I am given these odd balls one that I just don't know how to do. I was also asked to prove why it's not Θ if it is one of O or Ω, which I'm a little confused about as well.

Questions I was given:

f(n) = (n^3)/2 - 12n g(n) = n^2

f(n) = n g(n) = n^(1+sin(n))

This one is so confusing because g(n) is a wave so the they keep going over one another

Jared Lee
  • 5

1 Answers1

2

You just need to focus on $|f(n)/g(n)|$. If this ratio is bounded from above by a constant, then we have $f(n) \in O(g(n))$. If it is bounded from below by a constant, then we have $f(n) \in \Omega(g(n))$.

In the first example, we have $$|f(n)/g(n)| = \left|\frac{n^3/2 - 12n}{n^2}\right| = \left|\frac{1}{2} n - \frac{12}{n}\right|.$$ This is unbounded from above, but you can bound it from below by noting that it is $\ge 0.1$ for $n \ge 5$, and handle the other cases $n \in \{1,2,3,4\}$ directly.

In the second example we have $$|f(n)/g(n)|=\left|\frac{n}{n^{1+\sin n}}\right| = n^{-\sin n} \in [n^{-1}, n].$$ I think that as $n$ gets large, there will be values of $n^{-\sin n}$ that are close to $n$ and other values that are close to $n^{-1}$, so this ratio gets both arbitrarily large and arbitrarily close to zero.

angryavian
  • 89,882