1

I asked a similar question before I want to ask a follow up question on lower bounds or omega. For the following recurrence,

T2(n)=n2.001 + n2logn

T2(n)=O(n2.001). I have no problems with that. But I was also told that for lower bounds, T2(n)=Ω(n2.001) even though n2logn is supposed to be smaller than n2.0001. Help?

Community
  • 1
  • 1
Joseph D
  • 115
  • 7
  • 1
    Are we supposed to read `n^2logn` as `(n^2) log n` or as `n ^ (2 log n)`? – Jerry Coffin Sep 30 '15 at 15:34
  • Yesterday I told you that `T2(n)=n^2.001 + n^2logn = Ө(n^2.001)`. Since `Ө = O ∩ Omega` you can say `T2(n) = Omegan^2.001()` – sve Sep 30 '15 at 15:49
  • But why is T2(n)=omega(n^2.001) if (n^2.001)>(n^2 logn) at some large n... Wouldn't there be some k such that T(k) has complexity that is sandwiched between f(k)=k^2.001 and g(k)=(k^2 logk)? – Joseph D Sep 30 '15 at 16:00
  • Why would the lower bound on n^2 * log(n)...? – Christo S. Christov Oct 01 '15 at 10:27
  • @JosephD `T2(n)=Omega(n^2.001)` (big omega) and `T2(n)=omega(n^2)`. There is a big difference between small o and big O. `omega = '>'` and `Omega = '>='`. So your question is analogous to asking give me a lower of bound of `5`. People tell you that `5 >= 3` but a better lower bound for `5` is `5` itself since `5>=5`. Do you get it now? – sve Oct 02 '15 at 06:50

1 Answers1

1

Big Omega is used as a lower bound, so T2(n)=Ω(n^2 * logn) is perfectly valid. However, T2(n)=Ω(n^2.001) offers a tighter lower bound.

jh314
  • 27,144
  • 16
  • 62
  • 82