'What's the difference between big O and big Omega?

Big Omega is supposed to be the opposite of Big O, but they can always have the same value, because by definition Big O means:

g(x) so that cg(x) is bigger or equal to f(x)

and Big Omega means

g(x) so that cg(x) is smaller or equal to f(x)

the only thing that changes is the value of c, if the value of c is an arbitrary value (a value that we choose to meet inequality), then Big Omega and Big O will be the same. So what's the point of those two? What purpose do they serve?

algorithmbig-o


Solution 1:[1]

Big O is bounded above by (up to constant factor) asymptotically while Big Omega is bounded below by (up to constant factor) asymptotically.

Mathematically speaking, f(x) = O(g(x)) (big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x).

f(x) = ?(g(x)) (big-omega) means that the growth rate of f(x) is asymptotically greater than or equal to the growth rate of g(x)

See the Wiki reference below:

Big O notation

enter image description here

Solution 2:[2]

Sometimes you want to prove an upper bound (Big Oh), some other times you want to prove a lower bound (Big Omega).

http://en.wikipedia.org/wiki/Big_O_notation:

Family of Bachmann–Landau notations

Solution 3:[3]

You're correct when you assert that such a g exists, but that doesn't mean it's known.

In addition to talking about the complexity of algorithms you can also talk about the complexity of problems.

It's known that multiplication for example is ?(n) and O(n log(n) log(log(n))) in the number of bits, but a precise characterization (denoted by ?) is unknown. It's the same story with integer factorization and NP problems in general which is what the whole P versus NP thing is about.

Furthermore there are apparently algorithms and ones proven to be optimal no less whose complexity is unknown. See http://en.wikipedia.org/wiki/User:Erel_Segal/Optimal_algorithms_with_unknown_runtime_complexity

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 aa8y
Solution 3

Related Questions