O(1) - Constant

O(1) describes an algorithm that will always execute at the same time (or space) regardless of the size of the input data set.

int addition(int x, int y)
{
   return x + y;
}

O(log n) - Logarithmic

Algorithms with an order of log n generally reduce the problem size with each operation. The most common attributes of these algorithms are that:

• the choice of the next element on which to perform some action is one of several possibilities, and

• only one of these possibilities will need to be chosen.

int logarithmicExample(int n)
{
   while (n > 1)
   {
      n = n / 2;
   }
}

O(n) - Linear

O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

bool Contains(IList elements, int value)
{
   foreach (var element in elements)
   {
      if (element == value)
         return true;
   }
   return false;
}

Some examples of linear algorithms are:

• Finding the min/max element in a list

• Iteratively finding the nth Fibonacci number

O(n log n) - Linearithmic (Log linear)

O(n log n) describes an algorithm that performs an O(log n) operation for each item in the input.

Some efficient sort algorithms are in this category. Some examples of linearithmic algorithms are:

• Merge Sort

• Quick Sort

private static void Quick_Sort(int[] arr, int left, int right)
{
  if (left < right)
  {
    int pivot = Partition(arr, left, right);
    if (pivot > 1)
    {
      Quick_Sort(arr, left, pivot - 1);
    }    if (pivot + 1 < right)
    {
      Quick_Sort(arr, pivot + 1, right);
    }
  }
}

private static int Partition(int[] arr, int left, int right)
{
  int pivot = arr[left];
  while (true)
  {
    while (arr[left] < pivot)
    {
      left++;
    }    while (arr[right] > pivot)
    {
      right--;
    }    if (left < right)
    {
       if (arr[left] == arr[right])
         return right;
       int temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
    }
    else
    {
       return right;
    }
  }
}

O(n²) - Quadratic

O(n²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set.

Double nested loops are in this category. Some examples of quadratic algorithms are:

• Bubble Sort

• Selection Sort

public void Bubble_Sort(int[] input)
{
    bool hasSwapped;
    do
    {
        hasSwapped = false;
        for (var sort = 0; sort < input.Length - 1; sort++)
        {
            if (input[sort] > input[sort + 1])
            {
                var oldValue = input[sort + 1];
                input[sort + 1] = input[sort];
                input[sort] = oldValue;
                hasSwapped = true;
            }
        }
    } while (hasSwapped);
}

O(n³) - Cubic

O(n³) is almost the same as O(n²). Triple nested loops are used instead of double nested loops.

public void TripleLoop(int n)
{
   for(c=0; c<n; c++){
     for(i=0; i<n; i++){
       for(x=0; x<n; x++){
          a+=1;
       }
     }
   }
}

O(2^n) - Exponential

O(2^n) is an algorithm whose growth doubles with each addition to the input data set. Recursive calculations are in this category.

int Fibonacci(int number)
{
   if (number <= 1)
      return number;

   return Fibonacci(number - 1) + Fibonacci(number - 2);
}

Resources

Thanks for reading