CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Expressing the performance in diff. notations

1. Junior Member
Join Date
Aug 2009
Posts
3

## Expressing the performance in diff. notations

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.

2. ## Re: Expressing the performance in diff. notations

Ω(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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•