4. DSA with C++ - Big O Notation and Complexity Analysis

Big O Notation and Complexity Analysis

Big O Notation and complexity analysis: Big O Notation is a mathematical notation used to describe the upper bound or worst-case scenario of the time or space complexity of an algorithm. It provides a standardized way to compare algorithms and analyze their efficiency as the input size grows. The Big O Notation is represented as O(f(n)), where 'f(n)' represents the growth rate of an algorithm's time or space requirements. Here are some commonly used notations and their meanings:

1. O(1) - Constant Time Complexity: An algorithm has constant time complexity if its running time or space usage remains constant regardless of the input size. It is considered the most efficient. Examples include accessing an element in an array or performing a single operation.

    
   def print_first_element(arr):
       print(arr[0])
           

2. O(n) - Linear Time Complexity: An algorithm has linear time complexity if its running time or space usage grows linearly with the input size. Examples include iterating through an array or performing a single loop.

    
   def print_elements(arr):
       for element in arr:
           print(element)
           

3. O(n^2) - Quadratic Time Complexity: An algorithm has quadratic time complexity if its running time or space usage grows with the square of the input size. Examples include nested loops or performing operations on all pairs of elements.

    
   def print_all_pairs(arr):
       for i in range(len(arr)):
           for j in range(len(arr)):
               print(arr[i], arr[j])
           

4. O(log n) - Logarithmic Time Complexity: An algorithm has logarithmic time complexity if its running time or space usage grows logarithmically with the input size. Examples include binary search or divide-and-conquer algorithms.

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

5. O(n log n) - Linearithmic Time Complexity: An algorithm has linearithmic time complexity if its running time or space usage grows in a combination of linear and logarithmic terms. Examples include efficient sorting algorithms like Merge Sort or Quick Sort.

    
   def merge_sort(arr):
       if len(arr) <= 1:
           return arr
       mid = len(arr) // 2
       left = merge_sort(arr[:mid])
       right = merge_sort(arr[mid:])
       return merge(left, right)