Ai-CompTech

AI Computing

Computer Science Fundamentals

Algorithms: Big O Notation and Complexity Analysis

Master algorithm efficiency analysis and Big O notation

Intermediate 60 min read 0 examples 0 quiz questionsID: 6962f8e8
Lesson Content

Algorithms: Big O Notation and Complexity Analysis

Why Algorithm Analysis Matters

Scalability: Will your code work with 1 million users? Performance: Can you process data faster? Resource Management: Optimize CPU and memory usage Technical Interviews: Core topic at Google, Amazon, Facebook

What is Big O Notation?

Big O describes how runtime/space grows as input size increases.

Notation: O(f(n)) where n = input size

Focus: Worst-case scenario (upper bound)

Common Time Complexities

O(1) - Constant Time

Performance: Same time regardless of input size

Examples:

  • Array access by index
  • Hash table lookup
  • Push/pop on stack
code
def get_first(arr): return arr[0] # Always 1 operation # n=10 or n=1000000, same time!

O(log n) - Logarithmic Time

Performance: Halves search space each step

Examples:

  • Binary search
  • Balanced tree operations
code
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # n=1000 → ~10 steps # n=1000000 → ~20 steps

Growth:

  • n=10: 3-4 operations
  • n=100: 6-7 operations
  • n=1000: 10 operations
  • n=1000000: 20 operations

O(n) - Linear Time

Performance: Grows directly with input

Examples:

  • Linear search
  • Array traversal
  • Finding max/min
code
def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1 # n=100 → up to 100 operations # n=1000 → up to 1000 operations

O(n log n) - Linearithmic Time

Performance: Slightly worse than linear

Examples:

  • Merge sort
  • Quick sort (average)
  • Heap sort
code
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) # log n divisions right = merge_sort(arr[mid:]) return merge(left, right) # n operations per level # n=1000 → ~10,000 operations

Why faster than O(n²)?

  • n=1000: O(n²)=1,000,000 vs O(n log n)=10,000
  • 100x faster!

O(n²) - Quadratic Time

Performance: Nested loops over input

Examples:

  • Bubble sort
  • Selection sort
  • Insertion sort
  • Nested array comparisons
code
def bubble_sort(arr): n = len(arr) for i in range(n): # Outer loop: n for j in range(n-i-1): # Inner loop: n if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # n=100 → 10,000 operations # n=1000 → 1,000,000 operations!

Warning: Avoid for large datasets!

O(2ⁿ) - Exponential Time

Performance: Doubles with each input increase

Examples:

  • Recursive fibonacci (naive)
  • Tower of Hanoi
  • Subset generation
code
def fibonacci(n): if n <= 1: return n return fibonacci(n-1) + fibonacci(n-2) # n=10 → 1,024 calls # n=20 → 1,048,576 calls! # n=30 → Over 1 billion calls!

Solution: Use memoization!

O(n!) - Factorial Time

Performance: Extremely slow

Examples:

  • Traveling salesman (brute force)
  • Permutations
code
# n=10 → 3,628,800 operations # n=15 → Over 1 trillion operations!

Complexity Comparison Chart

| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | |---|------|----------|------|------------|-------|-------| | 10 | 1 | 3 | 10 | 33 | 100 | 1,024 | | 100 | 1 | 7 | 100 | 700 | 10,000 | 1.3×10³⁰ | | 1000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 | ∞ |

Space Complexity

Memory usage as input grows

O(1) Space:

code
def sum_array(arr): total = 0 # Single variable for num in arr: total += num return total

O(n) Space:

code
def create_copy(arr): return arr.copy() # New array of size n

Rules for Calculating Big O

1. Drop Constants

O(2n) → O(n) O(500) → O(1) O(n/2) → O(n)

2. Drop Non-Dominant Terms

O(n² + n) → O(n²) O(n + log n) → O(n) O(n³ + n² + n) → O(n³)

3. Different Inputs = Different Variables

code
def compare_arrays(arr1, arr2): for a in arr1: # O(a) for b in arr2: # O(b) if a == b: return True return False # Time: O(a × b), NOT O(n²)

4. Add for Sequential Steps

code
def process(arr): # Step 1 for x in arr: # O(n) print(x) # Step 2 for x in arr: # O(n) print(x * 2) # Total: O(n) + O(n) = O(2n) = O(n)

5. Multiply for Nested Steps

code
def nested(arr): for x in arr: # O(n) for y in arr: # O(n) print(x, y) # Total: O(n × n) = O(n²)

Practice Examples

Example 1:

code
def find_pairs(arr): for i in range(len(arr)): # O(n) for j in range(i+1, len(arr)): # O(n) print(arr[i], arr[j]) # Answer: O(n²) - nested loops

Example 2:

code
def process_data(arr): arr.sort() # O(n log n) for x in arr: # O(n) print(x) return arr[0] # O(1) # Answer: O(n log n) - dominant term

Example 3:

code
def search_matrix(matrix, target): for row in matrix: # O(rows) if target in row: # O(cols) return True return False # Answer: O(rows × cols)

Optimization Strategies

1. Use Hash Tables

O(n²) → O(n)

code
# Bad: O(n²) def has_duplicate_slow(arr): for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] == arr[j]: return True return False # Good: O(n) def has_duplicate_fast(arr): seen = set() for num in arr: if num in seen: return True seen.add(num) return False

2. Sort First

O(n²) → O(n log n)

3. Binary Search

O(n) → O(log n)

4. Memoization

O(2ⁿ) → O(n)

code
# Bad: O(2ⁿ) def fib_slow(n): if n <= 1: return n return fib_slow(n-1) + fib_slow(n-2) # Good: O(n) def fib_fast(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_fast(n-1, memo) + fib_fast(n-2, memo) return memo[n]

Real-World Impact

Facebook: O(n²) algorithm with 1 billion users

  • Operations: 1,000,000,000,000,000,000
  • Time: Years!

Google Search: O(n log n) with billions of pages

  • Fast enough for real-time results

Interview Tips

  1. Always analyze your solution
  2. State assumptions about input size
  3. Discuss tradeoffs (time vs space)
  4. Optimize if asked
  5. Use examples to verify

Practice Problems

  1. Analyze time complexity of quick sort
  2. Two sum problem - optimize to O(n)
  3. Find if array contains duplicates
  4. Reverse a linked list - space complexity
  5. Count inversions in array