LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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.

Notices

Reply
 
Search this Thread
Old 10-19-2003, 08:20 PM   #1
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 435

Rep: Reputation: 30
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.
 
Old 10-20-2003, 01:47 AM   #2
eric.r.turner
Member
 
Registered: Aug 2003
Location: Planet Earth
Distribution: Ubuntu
Posts: 208

Rep: Reputation: 31
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.
Old 10-20-2003, 08:29 AM   #3
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 435

Original Poster
Rep: Reputation: 30
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.
 
Old 08-05-2008, 10:20 AM   #4
btacoder
LQ Newbie
 
Registered: Aug 2008
Posts: 1

Rep: Reputation: 0
Big Omega in not Best Case

Quote:
Originally Posted by eric.r.turner View Post
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.
 
Old 05-25-2010, 02:21 PM   #5
sshine
LQ Newbie
 
Registered: May 2010
Posts: 2

Rep: Reputation: 1
Quote:
Originally Posted by eric.r.turner View Post
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.
Old 05-25-2010, 02:45 PM   #6
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
This thread is 7 years old!
 
Old 05-25-2010, 02:48 PM   #7
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 111Reputation: 111
Also note that something that is (for example) O(n) is O(n^2) as well, but O(n) is more useful and descriptive.
 
Old 05-26-2010, 07:18 AM   #8
sshine
LQ Newbie
 
Registered: May 2010
Posts: 2

Rep: Reputation: 1
Quote:
Originally Posted by tuxdev View Post
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 View Post
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Big, big hard drive in a little, little tablet... pengyou Linux - Laptop and Netbook 6 10-18-2004 03:44 AM
Big Noob Needs Big Help... HELP!!! UberNoober Linux - Software 8 03-12-2004 10:28 AM
Big, big Problem on vsftpd rhonneil Linux - Newbie 1 10-01-2003 02:18 PM
Installing RH 9 with RAID 5 --Big, big Problem!!! rhonneil Linux - Software 2 09-25-2003 08:13 PM
big BIG javascript & loading time luigi Programming 3 09-10-2001 03:53 AM


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

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration