Algorithm Analysis

Algorithm Analysis and the AP CS A Exam

By the end of this lesson, you will be able to analyze algorithm efficiency using Big-O notation, compare common algorithms, and prepare for AP exam algorithm questions.

Why Efficiency Matters

An algorithm that takes 1 second for n=1,000 might take:

• 1,000 seconds if O(n²)
• 10 seconds if O(n log n)
• 2 seconds if O(n)

For large inputs, the difference is enormous.

Big-O Notation

Big-O describes how an algorithm's running time (or space) grows relative to the input size n.

Big-O	Name	Example
O(1)	Constant	Array access, map lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search, one traversal
O(n log n)	Linearithmic	Merge sort, efficient sorting
O(n²)	Quadratic	Nested loops over n, selection sort
O(2ⁿ)	Exponential	Recursive Fibonacci (naive)

Analyzing Code

for (int i = 0; i < n; i++) {  // runs n times
    // O(1) work
}

Single loop: O(n)

Nested loops (both over n): O(n²)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {  // total: n × n = n² iterations
        // O(1) work
    }
}

Cutting the problem in half each time: O(log n)

// Binary search cuts the problem in half each step
// After k steps: n / 2^k = 1 → k = log₂(n)

Comparing Algorithms on the AP Exam

Selection sort: O(n²) — always; simple but slow for large data.

Insertion sort: O(n²) worst case, O(n) best case (already sorted).

Binary search: O(log n) — much faster than linear search for large arrays; requires sorted array.