Expressing the performance in diff. notations

[tarektarek]

Hi,
When we express the performance of an algorithm in terms of average, worst, and best cases, we often use the O-notation, however I sometimes see other notations and I do not know why we use them. Any guidance is appreciated.

Thanks in advance

[Zachm]

Ω(f(n)) (Omega notation) -
algorithm runs at least f(n) steps
(asymptotically - meaning, there is some k for which for every x > k the algorithm runs at least f(x) steps).
This is, of course, a simplification, but if you are trying to find an algorithm to solve a problem and not just analyze a given algorithm to solve a problem, it is often useful to know if you can or can't find an algorithm that solves this problem in less than f(n) steps.

Θ(f(n))(Theta notation) - best and worst complexities exhibit the same asymptotic behavior (grow at about the same speed).
If you have an algorithm for which you want to show that it will run the same time for any given input of length n - this notation is useful. Usually in the "real world" people want their algorithms to run as fast as possible, and therefore are satisfied with - "it won't run more than f(n) steps (asymptotically)", but the Θ(f(n)) notation gives a little bit more data, saying - "it won't run less than f(n) steps (asymptotically)".
Logically you might say that:
If an algorithms runs Ω(f(n)) steps and it also runs O(f(n)) steps, then this algorithm runs Θ(f(n)) steps.

Other notations are o("little-oh") and ω("little-Omega"), I find less useful in real world terms, others might think differently:
o(f(n)) means that the algorithm's complexity is O(f(n)) but not Θ(f(n)).
ω(f(n)) means that the algorithm's complexity is Ω(f(n)) but not Θ(f(n)).

Regards,
Zachm