Big O Notation. Exploring Time Complexity, Worst Case

Preface

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. For more detail https://en.wikipedia.org/wiki/Big_O_notation.

Inside the Software Industry this used to classify algorithms according to how their running time or space requirements grow as the input size grows. Big O notation tells you how fast an algorithm is.

”n is the size of input”. Result show that how your algorithm or your function perform result given input and execution time. Some of the common usage fastest to slowest:

• O(1) as Constant time complexity. Example : Accessing constant index array by index
• O(log n) Log time complexity. Example: Binary search.
• O(n) as Linear time complexity. Example: traversing an array, comparison of two strings, palindrome check, bucket sort
• O(n * log n) as Linear Logarithmic O. Example: A fast sorting algorithm, like merge sort, quicksort.
• O(n2) Quadratic O time complexity . Example: A slow sorting algorithm, like selection sort.
• O(n3) Cubic O time complexity. Example: Cubic for loop
• O(2^n) Exponential O time complexity. Example: This runtime complexity can be found in recursive functions.
• O(n!) Factorial O time complexity. Example: A really slow algorithm, like the travelling salesperson.

Logarithms or log: A mathematical concept/expression that’s used a lot in Computer Science.

• log2(8) is like asking “How many 2 do we multiply to get 8 ? which is 2 (2 * 2 * 2). So log2(8) = 3
• log b(n)=y means that b = base | y = exponent | n = Power (Result obtained by raising b to the power of y)

Our code is a cost to the system, meaning resources such as CPU, Memory, Disk and Network usages that computers have to use in order to execute. So that reason we need to aware performance while writing code. If you are Newbie, do not be afraid, as you become an expert this concept will stay in your mind.

Easiest way to find Big O Notation with Example

O(1) as Constant time complexity

give the best performance because algorithm is not dependent on the input size n, it is said to have a constant time complexity with order O(1). This means that the run time will always be the same regardless of the input size.

public int GetFirstElement(int[] arrayList)
{
 if (arrayList.Length == 0)
 {
  throw new IndexOutOfRangeException("Array is null or Empty");
 }
 return arrayList[0];

}

O(n) as Linear time complexity

Execution time of linear time algorithm is proportional to the input size. This means that when a function has an iteration that iterates over an input size of n, it is said to have a time complexity of order O(n).

Use Case : is traversing an array, comparison of two strings, palindrome check, bucket sort etc.

var sizeOfArray=arrayList.Length;

for(int index=0;index<sizeOfArray;index++){
  //statement is 0 , complexity is O(1)
  //statement is 1 , complexity is O(1)
  //statement is 2 , complexity is O(1)
  //statement is 3 , complexity is O(1)
  //statement is 4 , complexity is O(1)
}

Lets assume that we are 5 elements array our loop would be O(1+1+1+1+1)=O(5).
Therefore, total complexity of this entire code would be O(5 * n) = O(5n) = O(n).
5 becomes negligible our 

O(log n) Log time complexity.

In this approach data splitting chunks and discard a large amount every iteration.

Use Case : Binary search, Quick Sort

class QuickSort
    {
        public static void Sort(int[] arr, int left, int right)
        {
            if (left < right)
            {
                int pivot = Partition(arr, left, right);
 
                Sort(arr, left, pivot - 1);
                Sort(arr, pivot + 1, right);
            }
        }
 
        private static int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[right];
            int i = left - 1;
 
            for (int j = left; j < right; j++)
            {
                if (arr[j] <= pivot)
                {
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
 
            int tempVal = arr[i + 1];
            arr[i + 1] = arr[right];
            arr[right] = tempVal;
 
            return i + 1;
        }
}

O(n * log n) as Linear Logarithmic complexity .

In this approach every level a linear search is applying taking O(n) and in the next level the size of array reduced half which means in next level for search O(log n) will required. In every step a linear search and before moving to the next step the size of array reduced to half representing O(n log n).

Use Case: merge sort, heap sort and even quicksort

// https://www.geeksforgeeks.org/merge-sort/ 
// for more detail
using System;
 
class MergeSort {
 
    // Merges two subarrays of []arr.
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int[] arr, int l, int m, int r)
    {
        // Find sizes of two
        // subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        // Create temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];
        int i, j;
 
        // Copy data to temp arrays
        for (i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        // Merge the temp arrays
 
        // Initial indexes of first
        // and second subarrays
        i = 0;
        j = 0;
 
        // Initial index of merged
        // subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        // Copy remaining elements
        // of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        // Copy remaining elements
        // of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that
    // sorts arr[l..r] using
    // merge()
    void sort(int[] arr, int l, int r)
    {
        if (l < r) {
 
            // Find the middle point
            int m = l + (r - l) / 2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
}

O(n2) Quadratic O time complexity

in this case algorithm whose performance increases exponentially to the input data size.

Use Case: A slow sorting algorithm, like Bubble sort, Insertion sort ,Selection sort, or nested for loops

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ ){
    statement;
  }
}

excution time N*N

O(n3) Cubic O time complexity

Use Case: Cubic for loop

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ ){
    for ( k= 0; k< N; k++ ){
      statement;
    }
  }
}

excution time N*N*N

O(2^n) Exponential O time complexity

https://dev.to/lofiandcode/big-o-part-5-2-n-2ifn link exist amazing example.

Conclusion :

O(2^n) runtime complexities are often seen in recursive functions that make 
2 recursive calls and pass in the problem size of N-1.

If a recursive function makes more then one call, the complex is often
O(branches depth)

The base of an exponent does matter. O(2N) is very different from O(8N)

O(n!) Factorial O time complexity.

Use Case :

• the travelling salesperson.
• The Knapsack Problem
• The Clique Problem

Also O(n!) is the slowest algorithm.

For example the travelling salesperson problem lets assume 4 city

City List => city1 , city2 , city3 , city4

Permutation formula 4! is 4 * 3 * 2 * 1 => 24 . if cities count grow up solving problem cross a threshold requiring us to make millions and more calculations.

5! => 120
6! => 720
…

20! => 2432902008176640000