# 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. 

<figure><img src="https://2973098717-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FHpGtLEgTmWtkUT4PrDFL%2Fuploads%2FLHGYIx4iuU7Dv7Jn06qC%2Fimage.png?alt=media&#x26;token=4f07f54e-1e62-4b34-b10e-9f547eb1c614" alt=""><figcaption></figcaption></figure>

| 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 `2`and 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

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

 }

```

**Time Complexity:** O(1)

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

 }
```

**Time Complexity:** O(n)

```csharp
 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)

```csharp
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)

```csharp
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)

```csharp
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)

```csharp
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.