Big-O and Big-Omega Problem

jfhebb · 10-04-2010, 08:21 PM

So, I have a problem to show an example of a positive function f(n) so f(n) is neither O(n) or Ω(n). Any help?

dugan · 10-04-2010, 11:01 PM

I started writing an example (because this is an exceptionally easy question), but I thought better of it: doing your homework for you isn't right.

Hint: it's really easy to come up with a function involving nested loops where the best case and the worst case are both n-squared.

Berhanie · 10-04-2010, 11:04 PM

without getting into details, the idea is this: start with f which is not O(n), and g which is not Ω(n).
use those two functions to define another function h which is guaranteed to be neither O(n) nor Ω(n).