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.
+7
A:
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
2010-09-26 17:48:40
@Keith: How could you ever construct an algorithm taking a fractional number of steps?
Michael Madsen
2010-09-26 17:55:02
You can't. But that wasn't the question.
Keith Randall
2010-09-26 18:05:56
Then,is this a valid question in the first place?
Ringo
2010-09-26 18:17:46
Nice catch, I was thinking about algorithm as well. +1.
IVlad
2010-09-26 18:25:41
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
2010-09-26 18:25:45
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
Ringo
2010-09-26 18:37:22
@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
2010-09-26 18:53:55
So, Theta Θ(1) should be a constant, am I right?That cleared many doubts of mine.Thanks Christopher Creutzig, Keith Randall and others.
Ringo
2010-09-26 19:05:35
Also, by my understanding, O(1) and Ω(1) are disjount sets, is this correct?
Ringo
2010-09-26 19:11:36
@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
2010-09-26 19:20:53
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?
Ringo
2010-09-26 19:41:45
@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
2010-09-26 21:29:03
Ok, I got it. I was confused before asking this question. Now I it seemed to be clear. Thanks
Ringo
2010-09-26 23:53:21