Expressing the performance in diff. notations
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums
Results 1 to 2 of 2

Thread: Expressing the performance in diff. notations

  1. #1
    Join Date
    Aug 2009

    Expressing the performance in diff. notations

    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

  2. #2
    Join Date
    Oct 2006

    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)).


Posting Permissions

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

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

This is a survey!

HTML5 Development Center