1

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?

Santosh Panda
  • 7,235
  • 8
  • 43
  • 56
Martin Renee
  • 57
  • 1
  • 1
  • 2
  • 1
    `c` is not allowed to vary with `x`. Given `f` and `g`, there must be a particular `c` that makes the inequality true for all sufficiently large `x`. – user57368 May 13 '13 at 08:21

3 Answers3

0

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

David
  • 583
  • 1
  • 10
  • 27
-1

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

aa8y
  • 3,854
  • 4
  • 37
  • 62
Franck Dernoncourt
  • 77,520
  • 72
  • 342
  • 501
-1

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

M.J. Rayburn
  • 509
  • 4
  • 14