-1

Here's the question I'm working with

For each pair of expressions, indicate whether A is O, o, Ω, ω, or Θ of B.

enter image description here

I understand is pretty much the upper bound and omega is the lower bound and theta is both upper and lower bounds. I'm confused on what small o and small omega infers.

I'm fairly certain that A O of B in a since (n^3) > (n^2), but I'm not sure about everything else. I was wondering if someone could give me some steps on how to test each one. I've checked on wikipedia and some education sites but it's not very clear and there aren't many examples of testing them.

thanks

Jake Senior
  • 223
  • 4
  • 11
  • 4
    Offtopic. Not really a programming problem. Try http://cs.stackexchange.com/ – Marc B Apr 21 '15 at 18:15
  • See [this](http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on/471206#471206) for explanations of Landau (= "big Oh") notation. – G. Bach Apr 21 '15 at 18:43

1 Answers1

4

As taken from Big O notation on Wikipedia

The definitions of O-notation and o-notation are similar. The main difference lies is that in f(n)=O(g(n)), the bound 0<=f(n)<=c*g(n) holds for "some constant c>0", BUT ,in f(n)=o(g(n)), the bound 0<=f(n)<=o(g(n)) holds for "all constants c>0".

In o-notation, the function f(n) becomes insignificant relative to g(n) as n->∞ :-

enter image description here // for strict little-o notation

lim n->∞ f(n) / g(n) = c,     `c closer to 0`  // for strict Big-O notation

Similarly, for little-omega notation,

lim (x->infinity) f(x)/ g(x) = infinity

Whereas, for strict Big-Omega notation

lim n->∞ f(n) / g(n) = c,       `c closer to ∞`

So,now going through your questions,

1. lim n-> ∞ A(n)/B(n) = lim n-> ∞ {(4*n^3 - 12*n^2 + 5*n) / 36*n^2}
                         = lim n-> ∞ (n/9 - ...)
                         = ∞.

Hence, A(n) is ω(B(n)).

2. lim n -> ∞ A(n)/B(n) = lim n-> ∞ (5^n/n^5)
                        = lim n-> ∞ (5*5*5*...n times)/(n*n*n*n*n)
                        = Depends on the value of n

Hence, A(n) is Ω(g(n)).

The other two are being left for you as an exercise. If you have any problem,please leave further a comment. Good luck for solving your problems.

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
  • Wow. thank you so much. I'm pretty sure I understand all of that now. I was wondering if you could elaborate a little more on the 'c closer to infinity' and 'c closer to 0'. I was also wondering if you could explain how to find if it's big theta? Thank you so much for that detailed explanation it exceeded my expectations – Jake Senior Apr 22 '15 at 00:23
  • 1
    Also for number 2, wolfram alpha says the limit as n goes to infinity of A/B is infinity. so wouldn't it be little omega and not big O? – Jake Senior Apr 22 '15 at 00:28
  • @JakeSenior- You should better leave that part of `c being closer to 0 or infinity`. Also, Big-theta is the same as what you mentioned,nothing new can I add. But, for the second question,yes,I mistyped O in place of Ω. Thanks,but, it depends on the value of n too,hence, it will be Capital Ω,not the little-omega. Because,if you will proceed by your logic, then all the functions will be either little-o or little-omega. You need to make it Big-O or Big-omega wherever you're unsure about value of n. Hence, that `c closer to infinity`--- I hope you quiet understood. – Am_I_Helpful Apr 22 '15 at 05:39