0

How can two algorithms

  • one with O(n²)
  • the other with Ω(n)

have the same practical run time, when testing the algorithms with a large number?

Cœur
  • 37,241
  • 25
  • 195
  • 267
user3456374
  • 51
  • 4
  • 16
    How can someone whose height is greater than 1 meter be just as tall as someone whose height is less than 3 meters? – Douglas Zare May 06 '15 at 17:04
  • Big-O notation doesn't account for the coefficients. If the "faster" algorithm has a higher coefficient, you may need very large inputs for it to overtake the slower algorithm. – Barmar May 06 '15 at 17:06
  • 1
    This isn't even a question of coefficients; the OP is trying to compare worst-case running time to best-case running time. – chepner May 06 '15 at 17:17
  • @chepner, it's not about coefficient, but also not about worst/best-case distinction. O and Omega can both be applied to best/average/worst case runtime or any other function. – zch May 06 '15 at 17:28
  • dupe: http://stackoverflow.com/q/29972024/572670 (Don't want to single handedly close as dupe as I am the answerer, but it's basically a dupe) – amit May 06 '15 at 17:30
  • @chepner NO. Omega and O are NOT worst case VS best case perormance. They are upper bound VS lower bounds of functions. I explained it some time ago in [this thread](http://stackoverflow.com/a/12338937/572670). An algorithm can be worst case O(n^2) and best case O(n), and average case O(nlogn) - for example. There is no problem with that. big-O is set of *complexity functions* you can apply both analysis to big O and to big Omega. – amit May 06 '15 at 18:30
  • @chepner He does however compare lower bound with upper bound – amit May 06 '15 at 18:33
  • amit. Yes, I'm aware of that. In the context of the question, though, the OP is clearly talking about run-times modeled by functions with the given upper/lower bounds. – chepner May 06 '15 at 18:38
  • @chepner I am just commenting about the claim about comparing worst case to best case. It is not what he's doing. – amit May 06 '15 at 18:45
  • He is, unless he's making the worse mistake of describing the best-case running time of an algorithm as O(n^2) or the worst-case running time as Ω(n). "Best case O(n)" is a weak description, to the point of near uselessness, since it could leaves open the possibility that the best case is constant, logarithmic, or linear. – chepner May 06 '15 at 18:51

1 Answers1

2

O(f(n)) is a set of functions that grow proportionally to f(n) or slower.

Ω(f(n)) is a set of functions that grow proportionally to f(n) or faster.

There are many functions that grow at least as fast as n, but not faster than n^2. For example: n, n*log n, n^1.5, n^2.

zch
  • 14,931
  • 2
  • 41
  • 49
  • And when you compare a specific (smaller) n the linear factors matter for both as well. – eckes May 06 '15 at 19:24