4

Can some help me with a function which is Big O(1) but not Ω(1) and the other way around? Some explanation would greatly help.

NullUserException
  • 83,810
  • 28
  • 209
  • 234
rda3mon
  • 1,709
  • 4
  • 25
  • 37

1 Answers1

10

Big-O means <= and big Omega means >=, so a function that is O(1) but not Omega(1) is f(n) = 1/n. For the other way around, f(n) = n works.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • 3
    @Keith: How could you ever construct an algorithm taking a fractional number of steps? – Michael Madsen Sep 26 '10 at 17:55
  • 5
    You can't. But that wasn't the question. – Keith Randall Sep 26 '10 at 18:05
  • Then,is this a valid question in the first place? – rda3mon Sep 26 '10 at 18:17
  • Nice catch, I was thinking about algorithm as well. +1. – IVlad Sep 26 '10 at 18:25
  • 4
    The question is perfectly valid if you are just talking about functions. If a function represents an algorithm's running time, however, it must be at least 1. In any case, the reverse (Omega(1) but not O(1)) is perfectly valid. – Keith Randall Sep 26 '10 at 18:25
  • Then, it was my mistake to tag this in Algorithms. But, my feeling is, since O(1) is a constant, how can it bound any curve. Or may be just Theta(1) is only constant? I am just starting with algorithms, please bare with my silly questions – rda3mon Sep 26 '10 at 18:37
  • @Ringo: O(1) is a set. Namely the set of bounded functions. And n -> 1/n (for natural numbers n) is a member of that set. Ω(1) is another set, namely the set of functions bounded away from zero, and n -> 1/n is not a member of that set. Now, since the running time of an algorithm can not in any reasonable way (that I could imagine) decrease with larger inputs, *in the context of algorithmic complexity*, it is reasonable to treat algorithms with running time in O(1) as taking essentially constant time. – Christopher Creutzig Sep 26 '10 at 18:53
  • So, Theta Θ(1) should be a constant, am I right? That cleared many doubts of mine. Thanks Christopher Creutzig, Keith Randall and others. – rda3mon Sep 26 '10 at 19:05
  • Also, by my understanding, O(1) and Ω(1) are disjount sets, is this correct? – rda3mon Sep 26 '10 at 19:11
  • @Ringo: No, Θ(1) = O(1) ∩ Ω(1) is the set of all functions f which have a finite, non-zero limit. Which, for algorithmic complexity, is “essentially constant.” (Strictly speaking, Θ(1) is, of course, a constant. A constant set of functions. In the same sense that the sin function is a constant – the function itself does not change …) – Christopher Creutzig Sep 26 '10 at 19:20
  • Alright, I got your point. That was very helpful... Thank you. I have one more doubt, in cormen's Algorithm book, I read Θ(n^0) is same as Θ(1). How is this possible if Θ(1) = O(1) ∩ Ω(1), as O(1) has n^(1/2) as its function? – rda3mon Sep 26 '10 at 19:41
  • @Ringo, I'm confused by your question. O(1) does not have n^(1/2) in it. n^(1/2) grows with n. But n^(1/2) is in Omega(1). – Keith Randall Sep 26 '10 at 21:29
  • Ok, I got it. I was confused before asking this question. Now I it seemed to be clear. Thanks – rda3mon Sep 26 '10 at 23:53
  • @MichaelMadsen AFAIK There are Quantum Computing algorithms which might perform computations faster than amount of data - search in n elements in O(sqrt(n)) time. Till it's still theoretical, cause such Quantum hardware is not created yet, algorithms are beeing maid. (Currently created adiabiatic quantum computers, are only one of possible types). – Grzegorz Wierzowiecki Jan 11 '12 at 19:09