Analysis of the Limits of Algorithms

by Tony Vega

Submitted : Fall 2013

This is a report that will talk about the little o-notation of merge sort. The report will go over the concepts of merge sort, what it does, and how does it work; provided with actual code from the algorithm itself and detailed visualization that illustrates its nature because the reader must understand the sorting process of merge sort to understand the big O-notation which will then lead to the findings of the little o-notation. Big O-notation will briefly be over viewed in this report as it plays a key party in understanding the concept of little o-notation before using the mathematical tools that involve series and sequences. The Big O-notation states that: f(x) <= Cg(x) and as it turns out the big O of merge sort is: O(nlogn). In order to come to this conclusion the report will go over the “Master Theorem” and the simple binary tree.

As for little o-notation once the reader understands the concept of merge sort and big O-notation they will see that little o-notation doesn't differ that much from big O-notation except for the fact that there is only one big O of an algorithmic function as opposed to little o-notation there can be infinitely many. The little o-notation has two properties that the reader must keep in mind, firstly it states: f(x) <Cg(x) and secondly if the limit as x approaches infinity of g(x)/f(x) = 0, then that g(x) is the little o of f(x). In this case f(x) becomes f(n) which is the run time of the algorithm, or in other words the function which is: T(n) = 2T(n/2)+cn. At this point in the report it will start going over some mathematical tools needed to calculate the limit of this equation which in a way represents series, a fundamental part in calculus. In conclusion the little o-notation of merge sort turns out to be (n^2logn) or (n^klogn) for k can be any number => 2. This conclusion will get tested by the end of the report to see if it holds true.

[ Back ]