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.

A table showing the performance analysis of some sorting algorithms

*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:

• Data structures and algorithms
• How To Install Google’s Go Programming Language
• The Ten Commandments for C++ Programmers
• The History Of Carriage Return Line Feed
• Three Pitfalls To Avoid When Using Dynamically Allocated Memory

Tags: algorithms, programming