Big O, Omega, and SigmaDate: 09/19/2001 at 20:47:27 From: Jeremy Subject: Big O, Omega, and Sigma Hello, I think that I understand Big O and Omega notation (At large n, one is better/faster than another, and vice versa), but I cannot understand how something can be both Big O and Omega (aka Big Theta). I know that this specifies the order, but I can't get it. A general explanation of O/Omega/Theta (or a link to such) would be most helpful. Jeremy Date: 09/20/2001 at 15:38:41 From: Doctor Douglas Subject: Re: Big O, Omega, and Sigma Hi Jeremy, Thanks for writing to Dr. Math. Below are the definitions of big-oh, big-omega, and big-theta from the following Web page: Growth of Functions - Computer Science, Old Dominion University http://www.cs.odu.edu/~toida/nerzic/content/function/growth.html Definition (big-oh): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be O( g(x) ), which is read as f(x) is big-oh of g(x), if and only if there are constants C and n0 such that | f(x) | <= C | g(x) | whenever x > n0. Definition (big-omega): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be Omega( g(x) ) , which is read as f(x) is big-omega of g(x), if there are constants C and n0 such that | f(x) | >= C | g(x) | whenever x > n0. Definition (big-theta): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be Theta( g(x) ), which is read as f(x) is big-theta of g(x), if f(x) is O( g(x) ), and Omega( g(x) ). We also say that f(x) is of order g(x). Here is an example of how a function can be both big-o and big-omega: Consider the function f(x) = 5x^3 + x^2 + 1/(1+x^2). Without going through the complete details on the proof, it's apparent that f is O(x^3), since f(x) <= 7x^3 for x >= 1 (bounded above by Cx^3) f is Omega(x^3), since f(x) >= 5x^3 for x >= 1 (bounded below by Dx^3) Hence f is both O(x^3) and Omega(x^3), and thereby f is Theta(x^3) also. The above Web page also has more information on big-o, big-omega, and big-theta, as well as little-o and little-omega. I hope this helps. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/