Twitter
Algorithms are analyzed mainly on two categories. One is the speed of execution of the algorithm and the second is the memory requirement during the execution of the algorithm. The analysis of algorithms is important because it helps us make a decision as to which algorithm to use when we have a choice of algorithms. This is especially true in case of sorting algorithms which have a wide choice such as insertion sort, quick sort, merge sort, heap sort, counting sort, radix sort, etc.
Worst-Case Analysis
One method to analyze the performance of an algorithm is by the worst case performance of an algorithm. We can have a best case, average case and worst case analysis of any algorithm. However, the worst case analysis is the most convenient method to determine the performance of an algorithm. This is because the best case of an algorithm will not differ much from that of other algorithms, for example, in searching algorithms, the best case is that the element is found at the first search. It is quite often difficult to find the average case performance of an algorithm. The worst case of an algorithm places an upper bound on the performance of the algorithm which means the algorithm is guaranteed to perform as worse as it’s worst case and not more.
O-Notation
O-Notation is the most common notation used to express the performance of an algorithm. It expresses the worst case performance of an algorithm. An algorithms performance is measured in terms of the data that it processes.
O(1)
An algorithm is said to have a complexity of O(1) if it continues to execute in the same amount of time even with an increase in the data.
bool IsFirstElementEmpty(String[] strings)
{
if(strcmp(strings[0], "") == 0)
{
return true;
}
return false;
}
O(n)
An algorithm is said to have a complexity of O(n) if it’s performance decreases linearly with the amount of data that it handles.
bool ContainsValue(String[] strings, String value)
{
for(int i = 0; i < strings.Length; i++)
{
if(strcmp(strings[i] , value) == 0)
{
return true;
}
}
return false;
}
O(n²)
An algorithm is said to have a complexity of O(n2) if it's execution time increases by a factor of the square of it's input data.
bool ContainsDuplicates(String[] strings)
{
for(int i = 0; i < strings.Length; i++)
{
for(int j = 0; j < strings.Length; j++)
{
if(i == j)
{
continue;
}
if(strcmp(strings[i], strings[j]) == 0)
{
return true;
}
}
}
return false;
}
O(log n)
An algorithm which generally is based on a divide and conquer methodology with the division occuring at the middle of the input data set and continuing recursively is said to have a complexity of O(log n). Binary search which works by dividing the sorted data into half and working on each half recursively is said to have a complexityf of O(log n).
The following table shows how the performance degrades with the increase in the processing data of the algorithm.
| constant | logarithmic | linear | quadratic | cubic | ||
|---|---|---|---|---|---|---|
| n | O(1) | O(log N) | O(N) | O(N log N) | O(N2) | O(N3) |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 |
A table showing the performance analysis of some sorting algorithms
| Type of Sort | Best | Worst | Average | Comments |
|---|---|---|---|---|
| BubbleSort | O(N) | O(N2) | O(N2) | Not a good sort, except with ideal data. |
| Selection sort | O(N2) | O(N2) | O(N2) | Perhaps best of O(N2) sorts |
| QuickSort | O(N log N) | O(N2) | O(N log N) | Good, but it worst case is O(N2) |
| HeapSort | O(N log N) | O(N log N) | O(N log N) | Typically slower than QuickSort, but worst case is much better. |
*n or N is the number of elements of data that is being processed by the algorithm.
You can find more information at:
- http://rob-bell.net/categories/articles/
- http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html
Related Posts:
Tags: algorithms, programming
Helpful post. Thanks
[Reply]
InsertionSort is better than SelectionSort, because it has best-case complexity of O(N) (when input data is sorted). In addition, in my tests with random data it always performed better than SelectionSort (has lower constant in front of n^2, which is ommited in big-oh notation). All in all, it’s InsertionSort which is considered the best of O(n^2) sorting algorithms class.
[Reply]
Kevin Reply:
February 16th, 2010 at 5:09 pm
Insertion sort is the best if you already have input data sorted and want to sort the newly added element.
[Reply]
barnow Reply:
February 16th, 2010 at 7:24 pm
Of course, but this is only one of many advantages. Please read the wikipedia entry for more.
[Reply]