[throw149102]

I like to use the metaphor of driving somewhere, and trying to estimate when you're going to get there. Maybe you have a hotel reservation, and you want to make sure you don't get there too early nor too late. Then (with some times filled in for example):

  +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+
  |                   .                   | Best Case (little/no traffic) | Average Case (average traffic) | Worst Case (car accident, snow-in etc) |
  +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+
  | Max time, upper bound (Big O)         | 30 minutes                    | 45 minutes                     | 1 hour 20 minutes                      |
  | Both min and max, tight bound (Theta) | 25 minutes                    | 35 minutes                     | 1 hour                                 |
  | Minimum time, lower bound (Omega)     | 15 minutes                    | 25 minutes                     | 50 minutes                             |
  +---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+

So then you can start asking questions like - if I assume I'm in the average case, and I can show up earliest at 20 minutes from now, and show up latest at 50 minutes from now, can I guarantee that I will make it within that window? The answer in this case is yes, because our range is 25-45 minutes, so the earliest I can show up is in 25 minutes and the latest in 45 minutes.

This also helps explain why Big O is generally more useful - we can almost always be early to something, but we can almost never be late to something. So showing up 5 minutes early usually is not a problem.

It also shows why Theta is better than both - in this case, if we had this table we could completely ignore both the Big O row and Omega row, because Theta is a better bound for both min and max time.

Of course, in algorithmic complexity we replace the times with functions in terms of some variables, usually just n.

[tsimionescu]

Your example is nice, but extremely informal, as these are all constant numbers, while O/Theta/Omega (and o, omega, theta) are about functions.

I think the most important thing that needs to be clarified though is that algorithmic complexity is first and foremost a function, `WorseCaseComplexity(size of input) = max number of steps for any input of that size`. This function is often then classed into a "complexity class" using O/Theta/Omega etc, but that is only done for the sake of easier comparison of complexities between algorithms.

[charcircuit]

>It also shows why Theta is better than both

Big Theta for some functions is an empty set. Take for example bubble sort. It's O(n^2) and Ω(n), but there is no function that asymptotically bounds it above and below. In fact it is better if there isn't one as it means there exists fast cases. For bubble sort it's fast cases are ones where data is almost sorted and requires to scans of the array. If you know this is true of the input data you know bubble sort is more appropriate than something like merge sort which is Ω(nlog(n)). Now the O(n^2) worst case can still be significant so you may want to consider an alternate algorithm that doesn't break down as bad.

As the other reply pointed out we are talking about functions that bound some other function (in this context the amount of steps / operations / time an algorithm will take) when looking at how it behaves asymptotically.

[tsimionescu]

Note that "the amount of steps / operations / time an algorithm will take" is not in general a mathematical function, as for the same input size, different inputs will give different numbers of steps. For bubble sort for example there doesn't exist a function f(n) = number of steps bubble sort will take for an input of size n. There does exist a function best_case_complexity(n) = number of steps bubble sort will take for the best input of size n; and a function worst_case_complexity(n) = number of steps bubble sort will take for the worst input of size n.

Then, we can say best_case_complexity(n) = Theta(n), and worst_case_complexity(n) = Theta(n^2). We can also define the set of all functions representing the number of steps bubble sort will take for input of a certain "shape" of size n. We can then indeed say that any function in this set will be <= worst_case_complexity(n) and >= best_case_complexity(n), so this set will indeed be a subset of Omega(n) and of O(n^2).

[ahoka]

But I have the same table, but instead of time, I have the turns need to be taken by the car. That's not always useful.