BIG O Breakdown

What is Big O Notation?

Big O notation is a mathematical way to describe the time complexity or space complexity of an algorithm. It represents the worst-case growth rate of an algorithm as the input size $n$ increases, helping us understand how scalable an algorithm is.

Key Characteristics of Big O:

Focus on Growth: Big O focuses on how the number of operations grows with the size of the input ( $n$ ).
- Example: An algorithm that performs $2 n + 5$ operations is $O (n)$ because as $n$ grows, the constant $5$ and coefficient $2$ become negligible.

Worst-Case Analysis: It assumes the largest number of operations the algorithm might perform for the input size $n$ .

Ignore Constants and Lower-Order Terms:
- Constants don’t matter in Big O because they don’t scale with $n$ .
- Example: $O (2 n) = O (n)$ , $O (n + 10) = O (n)$ .

Only the Dominant Term Counts:
- If an algorithm has multiple terms like $O(n^2 + n)$ , the term with the fastest growth rate dominates. So, $O(n^2 + n) = O(n^2)$ .

Common Big O Complexities

Complexity	Name	Description
$O (1)$	Constant	Takes the same amount of time regardless of input size.
$O(log⁡n)O(\log n)$	Logarithmic	Reduces the problem size by half at every step.
$O (n)$	Linear	Time grows directly proportional to the input size.
$\log n)$	Linearithmic	Common in efficient sorting algorithms like Merge Sort.
$O(n^2)$	Quadratic	Common in nested loops, grows rapidly with input size.
$O(2^n)$	Exponential	Doubles operations for each increment in input size.
$O (n!)$	Factorial	Infeasible for even moderately large input sizes.

How to Calculate Big O

To calculate Big O, analyze the algorithm step by step, focusing on loops, function calls, and recursive depth.

1. Loops

A loop that runs $n$ times is $O (n)$ .

Nested loops multiply their complexities.
- Example:
  
  python
  
  for i in range(n): # O(n) for j in range(n): # O(n) print(i, j) # O(1)
  
  Total = $\cdot O(n) = O(n^2)$ .

2. Sequential Steps

If an algorithm has multiple parts, add their complexities.
- Example:
  
  python
  
  for i in range(n): # O(n) print(i) # O(1) for j in range(m): # O(m) print(j) # O(1)
  
  Total = $O (n) + O (m)$ .

If $n = m$ , the total is $O (n) + O (n) = O (2 n) = O (n)$ .

3. Function Calls

If a function is called recursively, analyze how many times it is called and the work done in each call.
- Example (Binary Search):
  
  python
  
  def binary_search(arr, target, left, right): if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, right) else: return binary_search(arr, target, left, mid - 1)
  - Binary search splits the array into halves, so its complexity is $O(log⁡n)O(\log n)$ .

4. Recurrence Relations

Recursive algorithms often have recurrence relations.
- Example (Merge Sort):
  - Merge Sort divides the array into halves and merges them back.
  - Relation: $T (n) = 2 T (n /2) + O (n)$ (two recursive calls + merge operation).
  - Complexity: $\log n)$ .

Practical Examples

Example 1: Single Loop

Total = $O (n)$ .

Example 2: Nested Loop

Total = $\cdot O(n) = O(n^2)$ .

Example 3: Sorting and Traversal

Total = $\log n) + O(n) = O(n \log n)$ .

Example 4: Binary Search

Complexity: $O(log⁡n)O(\log n)$ , because the array size is halved in each recursive call.

Tips for Calculating Big O

Focus on Loops: Count how many times each loop runs.

Break Down Steps: Analyze each segment of the algorithm separately.

Remove Constants: Ignore constants and lower-order terms.

Understand Recursive Depth: For recursive algorithms, determine how the input size shrinks with each call.

With practice, determining Big O becomes intuitive!