Latest LQ Deal: Latest LQ Deals
 LinuxQuestions.org Big O, Big Omega, and Big Theta
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

 10-19-2003, 08:20 PM #1 oulevon Member   Registered: Feb 2001 Location: Boston, USA Distribution: Slackware Posts: 438 Rep: Big O, Big Omega, and Big Theta I'm confused between Big O, Big Omega, and Big Theta notations. I understand that Big O gives you an upper bound which gives you the worst case growth rate of the function. And Big Omega gives you a lower bound or best case growth rate of the function, and a function that has an upper and lower bound of the same order is Big Theta. Does this explicitly mean that Big O is worst case; Big Omega is best case, and Big Theta is the average? That's the way I believed it to be, but then this confused me: Insertion Sort has a worst and average case of Big O(n^2) and Big Theta (n^2) respectively, and a best case of Big Omega (n). Those are two different functions: one is quadratic (n^2) and the other is linear (n), wouldn't you need to find separate lower and upper bounds on them? Any help would be appreciated. This has been confusing me for a while.
 10-20-2003, 01:47 AM #2 eric.r.turner Member   Registered: Aug 2003 Location: Planet Earth Distribution: Linux Mint Posts: 216 Rep: Big Theta is not the average runtime. It only describes the case where the upper and lower bounds of a function are on the same order of magnitude. As far as I know there is no asymptotic notation to describe the average runtime of a function. You are correct that Big O describes the upper (worst case) bound, and Big Omega describes the lower (best case) bound. Insertion Sort has an upper bound of O(n^2) and a lower bound of Omega(n). Big Theta notation does not apply to Insertion Sort, even though Insertion Sort has an average runtime. 1 members found this post helpful.
 10-20-2003, 08:29 AM #3 oulevon Member   Registered: Feb 2001 Location: Boston, USA Distribution: Slackware Posts: 438 Original Poster Rep: Eric, Thanks for your reply. My book says that Insertion Sort is Big Theta of n^2 after it says that it has a best case running time of n-1 comparisons, but they don't go on to explain why it's Big Theta of n^2. Is this simply because it n(n-1)/2 can be bounded from below as well? Thanks for your help.
08-05-2008, 10:20 AM   #4
btacoder
LQ Newbie

Registered: Aug 2008
Posts: 1

Rep:
Big Omega in not Best Case

Quote:
 Originally Posted by eric.r.turner Big Theta is not the average runtime. It only describes the case where the upper and lower bounds of a function are on the same order of magnitude. As far as I know there is no asymptotic notation to describe the average runtime of a function. You are correct that Big O describes the upper (worst case) bound, and Big Omega describes the lower (best case) bound. Insertion Sort has an upper bound of O(n^2) and a lower bound of Omega(n). Big Theta notation does not apply to Insertion Sort, even though Insertion Sort has an average runtime.

I believe Big Omega is not best case scenario. It is only a notation to state the minimum lower bound that can be defined for the running time. It only states that f(n) dominates g(n) for all values of n. If we define minimum time to be the best case scenario, only then we could call it best case.

05-25-2010, 02:21 PM   #5
sshine
LQ Newbie

Registered: May 2010
Posts: 2

Rep:
Quote:
 Originally Posted by eric.r.turner Big Theta is not the average runtime. It only describes the case where the upper and lower bounds of a function are on the same order of magnitude. As far as I know there is no asymptotic notation to describe the average runtime of a function. You are correct that Big O describes the upper (worst case) bound, and Big Omega describes the lower (best case) bound. Insertion Sort has an upper bound of O(n^2) and a lower bound of Omega(n). Big Theta notation does not apply to Insertion Sort, even though Insertion Sort has an average runtime.
Be careful not to confuse best/average/worst case with asymptotic bounds. Big O describes the asymptotic upper bound, but can do so for all three cases. Big Omega likewise can describe an asymptotic lower bound in all three cases. Some of these bounds make less sense than others:

In case of insertion sort: Its best-case running time is O(n) and Omega(n) and therefore Theta(n). It will neither go faster nor slower than the time it takes to process all n elements. Its average-case running time is O(n^2): When sifting element A[e] down array A, it will on average be compared with half of the n elements of A[1..e-1], and since n/2 is proportional to n by a constant factor, insertion sort has an average-case running time of O(n^2). A lower bound for its average-case running time can be defined in a number of complicated ways.

1 members found this post helpful.
 05-25-2010, 02:45 PM #6 MTK358 LQ 5k Club   Registered: Sep 2009 Posts: 6,443 Blog Entries: 3 Rep: This thread is 7 years old!
 05-25-2010, 02:48 PM #7 tuxdev Senior Member   Registered: Jul 2005 Distribution: Slackware Posts: 2,012 Rep: Also note that something that is (for example) O(n) is O(n^2) as well, but O(n) is more useful and descriptive.
05-26-2010, 07:18 AM   #8
sshine
LQ Newbie

Registered: May 2010
Posts: 2

Rep:
Quote:
 Originally Posted by tuxdev Also note that something that is (for example) O(n) is O(n^2) as well, but O(n) is more useful and descriptive.
Yes, O(n) would be a tighter bound and would better describe the runtime complexity of the algorithm. This means that the algorithm is also o(n^2) (little-o of n-squared). Like little-o is the untight counterpart to Big-O, little-omega (ω) is the untight counterpart to Big-Omega (Ω).

Quote:
 Originally Posted by MTK358 This thread is 7 years old!
The reason I replied was because the thread had a high search engine rating and asks a good question, but the answer lacked some details. Hopefully when people encounter this thread asking the same question, they will learn more. I hope this has not offended anyone.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post pengyou Linux - Laptop and Netbook 6 10-18-2004 03:44 AM UberNoober Linux - Software 8 03-12-2004 10:28 AM rhonneil Linux - Newbie 1 10-01-2003 02:18 PM rhonneil Linux - Software 2 09-25-2003 08:13 PM luigi Programming 3 09-10-2001 03:53 AM

LinuxQuestions.org

All times are GMT -5. The time now is 02:28 PM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -