Big O

Big O notation in computer science is a mathematical notation used to describe the performance or complexity of an algorithm. It specifically measures the worst-case scenario, or the maximum amount of time an algorithm takes to complete as the size of the input data increases.

Big O Notation	Description
O(1)	Constant Time: The running time of the algorithm is constant. It does not grow with the size of the input.
O(log ⁡n)	Logarithmic Time: The running time grows logarithmically with the size of the input
O(n)	Linear Time: The running time grows linearly with the size of the input.
O(n log ⁡n)	Log Linear Time: The running time grows in proportion to n log n.
O(n^2)	Quadratic Time: The running time grows quadratically with the size of the input.
O(2^n)	Exponential Time: The running time grows exponentially with the size of the input.
O(n!)	Factorial Time: The running time grows in proportion to the factorial of the input size.

Rules

1. Always consider Worst Case.

2. Remove Constants e.g O(2n). Here, drop constant 2and it would be O(n).

3. Different terms for inputs e.g. O(a+b), O(a*b).

4. Drop non dominants e.g. O(n), O(n^2). Here, drop O(n) which is non dominated as compare to O(n^2).

NOTE:

• n: Represent the number of elements.

• H: Represent height (Depth) of graph and tree.

• L: Represent the length of string etc.

Examples

 public static void Function()
 {
     for (int i = 0; i < 5; i++) // constant time
     {
         Console.WriteLine(i); 
     }

 }

Time Complexity: O(1)

 public static void Function(int number)
 {
     for (int i = 0; i < number; i++)
     {
         Console.WriteLine(i); // N times
     }

 }

Time Complexity: O(n)

 public static void Function(int number)
{
    for (int i = 0; i < number; i++)
    {
        Console.WriteLine(i); 
        for (int j = 0; j < number; j++)
        {
            Console.WriteLine(j); // N*N times
        }
    }

}

Time Complexity: O(n^2)

public static void Function(int number)
{
    for (int i = 0; i < number; i++) // N times
    {
        Console.WriteLine(i);
        for (int j = 1; j <= number; j *= 2) // log N times 
        {
            Console.WriteLine(j);
        }
    }

}

Time Complexity: O(n log n)

public static void Function(int number)
{
    for (int i = 1; i < number; i++) // N times
    {
        Console.WriteLine(i);
        for (int j = 1; j <= number; j += i) // log N times  as J increasing rate of i
        {
            Console.WriteLine(j);
        }
    }

}

Time Complexity: O(n log n)

public static void Function(int number)
{
    int i = 1;
    while (i < number)
    {
        int j = number;
        while(j>0)
        {
            j = j / 2; //log N times
        }

        i = 2 * i; // log N times
    }

}

Time Complexity: O(log n * log n) = O(log^2 n)

public static void Function(int number)
{
    int i = 1;
    while (i < number)
    {
        i = 2 * i; // log N times
    }

    for (int j = 0; j < number; j++)
    {
        Console.WriteLine(j);
        for (int k = 0; k < number; k++) //N*N times
        {
            Console.WriteLine(k);
        }
    }

}

Time Complexity: O(log n n^2) = O(n^2) drop no dominated (log n) complexity.