Big O Notation Lecture Notes

Introduction to Big O Notation

• Purpose: Classify algorithms based on growth rates of time and space.
• Importance: Essential for writing efficient algorithms.
• Presentation by: Giorgio Thompson.

Definition of Big O Notation

• Definition: Analyzes algorithm efficiency as input sizes approach infinity.
• Example: A dentist treating patients in linear time (O(n)).
  • Treats each patient in a constant time (e.g., 30 mins), so total time scales with the number of patients.

Time Complexity Basics

• Constant Time (O(1)): Not affected by input size.
  • Example: A function that performs a constant calculation.
• Linear Time (O(n)): Time grows linearly with input size.
  • Example: Iterating through an array of size n.

Important Concepts

• Constants: Values that do not change with input size; ignored in Big O notation.
• Growth Hierarchy:
  • O(1) (best) < O(n) < O(n^2) < O(n^3) < ... (worst)

Examples of Time Complexities

• O(n^2): Example with nested loops.
• O(n^3): Example with three nested loops.
• O(log n): Example with a recursive function that halves the input.

Understanding Logarithmic Complexity (O(log n))

• Logarithm: The power to which a base must be raised to produce a given number (e.g., log base 2 of 8 is 3).
• Binary Search: Efficient algorithm that works on sorted arrays, reducing the search space by half each time.

Recursive Functions & Complexity

• Example: Recursive Fibonacci function behaves exponentially (O(2^n)).
• Each call to the function results in two further calls, creating a binary tree of calls.

Space Complexity

• Definition: Memory used by an algorithm in relation to input size.
• Example: Recursive calls stack up in memory; for n=5, there are 5 calls on the stack.
• Space Complexity of O(n) for this example.

Common Mistakes in Big O Analysis

1. Assuming Nested Loops: Two consecutive loops are O(n) each, so total is O(n + n) = O(n) not O(n^2).
2. Separate Inputs: Two loops over different inputs (A and B) results in O(A + B) for consecutive loops, and O(A * B) for nested loops.
3. Ignoring Base Cases: Ensure to account for base cases in recursive calls when analyzing complexity.*

Conclusion

• Big O notation is a critical tool for analyzing algorithm efficiency.
• Understanding growth rates helps in writing performant code.