Posted by: Jesse | October 3, 2011

HW2 stats:

• Mean: 68
• Median: 70
• Standard Deviation: 23

There seems to be some confusion on the difference between O(), Ω(), and θ()  which I will attempt to clear up here.  All algorithm will have a definite runtime, say f(n), for which it is θ(f(n)).  This means that the algorithm will take time which is asymptotically equivalent to f(n) on its worst case input.  When analyzing an algorithm for its runtime, we can say its f(n) is at most some function g(n) which is an upper bound.  Meaning that we know the algorithm will take g(n) time or less on its worst case input.  Then we would say that the function is O(g(n)).  Similarly, we can prove that an algorithm will take at least h(n) time asymptotically on its worst case input.  Then we would say the algorithm is Ω(h(n)), or it is lower bounded by h(n).  To say the the upper and lower bounds are tight, means that g(n) = θ(h(n)) = θ(f(n)) and the algorithm is θ of all three of these functions(which can all be the same).  The important thing to note here is that we are always concerned with the worst case input to the algorithm.

If this is still unclear, or if you want to do some extra reading on asymptotic notation, check out this link.  The author does a good and accurate job of explaining this without requiring much background from the reader.  Please be aware that this link is not mathematically precise and may be missing some details.  I think it does serve well as an informal introduction to the topic.  http://eternallyconfuzzled.com/arts/jsw_art_bigo.aspx