What is Big O Notation? Explain me in the easiest way with examples

Big O Notation is a mathematical way of describing how the performance of an algorithm (specifically its time complexity or space complexity) grows as the size of the input increases. It gives you an upper limit on the growth rate, helping to analyze the efficiency of algorithms.

**Key Points:**
1. **Growth Rate**: Big O focuses on the most significant factors that affect this growth. It ignores constants and lower-order terms, which have less impact when the input size is very large.
2. **Worst Case**: It often describes the worst-case scenario, helping to set expectations on how long an algorithm will take to run or how much memory it will need.

### Common Big O Notations

1. **O(1)** - Constant Time
   - The algorithm takes the same amount of time regardless of the input size.
   - **Example**: Accessing an element in an array by index.

     ```python
     def get_element(array, index):
         return array[index]  # Always takes the same time
     ```

2. **O(log n)** - Logarithmic Time
   - The algorithm's time increases logarithmically as the input size increases, often found in algorithms that divide the input in each step, like binary search.
   - **Example**: Binary search in a sorted array.

     ```python
     def binary_search(array, target):
         low, high = 0, len(array) - 1
         while low <= high:
             mid = (low + high) // 2
             if array[mid] == target:
                 return mid
             elif array[mid] < target:
                 low = mid + 1
             else:
                 high = mid - 1
         return -1
     ```

3. **O(n)** - Linear Time
   - The time increases linearly with the input size. If you double the input, the time doubles.
   - **Example**: Finding a specific value in an unsorted list.

     ```python
     def linear_search(array, target):
         for i in array:
             if i == target:
                 return True
         return False
     ```

4. **O(n log n)** - Linearithmic Time
   - More efficient than O(n²), often found in efficient sorting algorithms, like mergesort or heapsort.
   - **Example**: Mergesort.

     ```python
     def merge_sort(array):
         if len(array) > 1:
             mid = len(array) // 2
             left_half = array[:mid]
             right_half = array[mid:]

             merge_sort(left_half)
             merge_sort(right_half)

             i = j = k = 0

             while i < len(left_half) and j < len(right_half):
                 if left_half[i] < right_half[j]:
                     array[k] = left_half[i]
                     i += 1
                 else:
                     array[k] = right_half[j]
                     j += 1
                 k += 1

             while i < len(left_half):
                 array[k] = left_half[i]
                 i += 1
                 k += 1

             while j < len(right_half):
                 array[k] = right_half[j]
                 j += 1
                 k += 1
     ```

5. **O(n²)** - Quadratic Time
   - The time increases quadratically with the input size. Common in algorithms that use nested iterations over the data.
   - **Example**: Bubble sort.

     ```python
     def bubble_sort(array):
         n = len(array)
         for i in range(n):
             for j in range(0, n-i-1):
                 if array[j] > array[j+1]:
                     array[j], array[j+1] = array[j+1], array[j]
     ```

### Summary
- Big O Notation helps evaluate the efficiency of algorithms based on their time or space requirements as a function of input size.
- By understanding Big O, you can compare algorithms and choose the best one for large inputs!