What is Big O Notation and Asymptotic Analysis of Algorithms?

• What is Big-O Analysis?
• How Does Big-O Analysis Work?
• How to Do Big-O Analysis?

What is Big-O Analysis?

Big-O notation is an asymptotic analysis method for measuring an algorithm's time complexity. Because big-O notation is asymptotic, it gives approximate estimate. Asymptotic notations are used when no exact estimates can be computed. Big O notation is an upper bound of an algorithm's run time complexity. Big-O notation for asymptotic analysis was introduced by Paul Bachmann in 1894 and popularized in subsequent years by Edmund Landau and others.

In big-O analysis, we analyze an algorithm's run time complexity for an input size. For a while, assume that input size is n (for an example, n could be the number of elements in an array or number of nodes in a linked list or the number of bits in a data type or something else depending upon what problem is being solved). After figuring out what n is in terms of the input, we have to determine how many times the n input items are examined in terms of n assuming that every operation or iteration or examination is equivalent and takes constant time.

How Does Big-O Analysis Work?

To understand big-O analysis, we develop a small C function returnMax which takes an array of integers of size n and returns the largest element among array elements.

/* C function to return the largest element from an array. */
 
#include <stdio.h>
#define N 10
 
/* Returns the largest integer in the array */
int returnMax(int array[], int n)
{
  int curMax, i;
  /* Make sure array size is not zero. */
  if (n <= 0)
    return -1;
 
  /* Initially set the largest number to the first array element. */
  curMax = array[0];
 
  /* Compare every element with the largest one till now. */
  for (i = 1; i < n; i++)
  {
    if (array[i] > curMax)
    {
      curMax = array[i];
    }
  }
  return curMax;
}
 
int main (void)
{
  int arr[10] = {1, 9, 2, 8, 3, 7, 4, 6, 10, 5};
  int max;
 
  max = returnMax(arr, N);
  printf("%d is the largest element in the array.\n");
 
  return 0;
}
 
OUTPUT
======
10 is the largest element in the array.

In above C function returnMax, "examine" means comparing an array value to another value. In returnMax, each array element was compared once to a maximum value. Thus, the n input items are each examined once, resulting in n examinations. This is considered O(n), usually referred to as linear time: The time required to run the algorithm increases linearly with the number of input items. You may have noticed that in addition to examining each element once, there is a check to ensure that the array is not empty and a step that initializes the curMax variable. It may seem more accurate to call this an O(n + 2) function to reflect these extra operations. Big-O analysis, however, yields the asymptotic running time, the limit of the running time as n gets very large. As n approaches infinity, the difference between n and n + 2 is insignificant, so the constant term can be ignored. Thus, in big-O analysis we eliminate all but the highest-order term, the term that is largest as n gets very large. In this case, n is the highest-order term. Therefore, the returnMax function is O(n).

The fastest-possible running time for any run-time analysis is O(1), commonly referred to as constant running time. An algorithm with constant running time always takes the same amount of time to execute, regardless of the input size.

How to Do Big-O Analysis?

The general procedure for big-O run-time analysis is as follows:

1. Figure out what the input is and what n represents.
2. Express the number of operations the algorithm performs in terms of n.
3. Eliminate all but the highest-order terms.
4. Remove all constant factors.

Big-O analysis should be straightforward if we are able to identify the input size, and the operations correctly that are dependent on the input size.