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

Thread: Expressing the performance in diff. notations

  1. #1
    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.

    Thanks in advance

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center