Big O Notation

Imagine you have a phone book with 1,000,000 names. You need to find 'John Smith'.

Approach 1: Check every page

• Look at page 1: Not here
• Look at page 2: Not here
• ... repeat 1,000,000 times
• Time: ~10 hours

Approach 2: Open to the middle

• 'Smith' starts with S, so go to middle
• 'M' is before 'S', so go to right half
• Repeat until found
• Time: ~20 seconds

Same problem. Same data. Dramatically different performance.

The Core Insight

An algorithm is a step-by-step procedure for solving a problem. The quality of your algorithm determines how fast your solution runs.

As an Amazon SDE-1, you will write code that processes:

• Millions of customer orders
• Billions of search queries
• Terabytes of log data

A slow algorithm isn't just inconvenient—it's expensive. Amazon spends millions on compute resources. Your ability to write efficient code directly impacts the bottom line.

What You'll Learn

This topic teaches you to predict how fast your code will run before you write it. This skill separates junior developers from senior engineers.

Key Terms

• Algorithm: A finite sequence of steps to solve a problem
• Efficiency: How much time and memory an algorithm uses
• Scalability: How performance changes as input grows

The Problem with Timing Code

You might think: "Just run the code and measure how long it takes."

This approach fails because:

1. Hardware differences: Your laptop vs Amazon's servers
2. Input variation: Sorting [1,2,3] vs [9,8,7,6,5,4,3,2,1]
3. Language differences: Java vs Python vs C++
4. System load: Other processes running
5. Compiler optimizations: Different builds

The Solution: Abstract Analysis

Instead of measuring actual time, we count operations.

// How many operations?
for (int i = 0; i < n; i++) {
    System.out.println(i);
}

This loop runs n times. Regardless of:

• Your computer's speed
• The programming language
• The system load

It always does n operations.

Why This Works

If Algorithm A does n operations and Algorithm B does n² operations:

• For n=10: A=10, B=100 (10x slower)
• For n=100: A=100, B=10,000 (100x slower)
• For n=1,000: A=1,000, B=1,000,000 (1000x slower)

The ratio stays consistent regardless of hardware.

The Abstraction

We don't count exact operations. We count growth rate.

Instead of saying "this code does 3n² + 5n + 100 operations", we say "this code is O(n²)".

Why? Because for large n, only the dominant term matters.

n	3n² + 5n + 100	n²	Ratio
10	450	100	4.5
100	30,500	10,000	3.05
1000	3,005,100	1,000,000	3.005

As n grows, the ratio approaches 3. The constant doesn't matter for large inputs.

Time complexity measures how many operations an algorithm performs relative to input size.

Counting Operations

// Example 1: Single loop
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}
// Operations: n
// Time Complexity: O(n)

// Example 2: Nested loops
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}
// Operations: n × n = n²
// Time Complexity: O(n²)

// Example 3: Halving
while (n > 1) {
    n = n / 2;
}
// Operations: log₂(n)
// Time Complexity: O(log n)

Common Time Complexities

Complexity	Name	Example	n=1000 operations
O(1)	Constant	Array access	1
O(log n)	Logarithmic	Binary search	10
O(n)	Linear	Single loop	1,000
O(n log n)	Linearithmic	Merge sort	10,000
O(n²)	Quadratic	Nested loops	1,000,000
O(n³)	Cubic	Triple nested	1,000,000,000
O(2ⁿ)	Exponential	Subset generation	10³⁰¹

Visual Growth

Operations
|
|                                          O(2ⁿ)
|                                        *
|                                      *
|                                    *
|                                  *
|                                *
|                              *
|                           *
|                       * O(n²)
|                  * *
|             * *
|        * * O(n log n)
|   * * * O(n)
|* * * * * O(log n)
|* * * * * * * O(1)
+-------------------------------------> Input Size (n)

How to Identify

1. Single loop over n: O(n)
2. Nested loop over n: O(n²)
3. Loop that halves: O(log n)
4. Loop that doubles: O(log n)
5. Recursive calls that split in half: O(log n)
6. Recursive calls that double: O(2ⁿ)

Space complexity measures how much memory an algorithm uses relative to input size.

Why Space Matters

Amazon servers have limited memory. If your algorithm uses too much memory:

• You can't handle large datasets
• You might crash the server
• You'll increase costs (memory isn't free)

Counting Space

// Example 1: No extra space
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}
// Space: 2 variables (sum, i)
// Space Complexity: O(1)

// Example 2: Extra array
int[] result = new int[n];
for (int i = 0; i < n; i++) {
    result[i] = i * 2;
}
// Space: n elements
// Space Complexity: O(n)

// Example 3: 2D array
int[][] grid = new int[n][n];
// Space: n × n elements
// Space Complexity: O(n²)

Common Space Complexities

Complexity	Example	What it means
O(1)	Fixed variables	Same space regardless of input
O(log n)	Binary search recursion	Stack depth = log n
O(n)	Extra array	Space grows with input
O(n²)	2D grid	Space grows quadratically

Input Space vs Extra Space

When analyzing space, we typically measure extra space (excluding input):

// Input: array of n elements (already exists)
// Extra space: 1 variable
int max = array[0];
for (int i = 1; i < array.length; i++) {
    if (array[i] > max) max = array[i];
}
// Space Complexity: O(1)

Time-Space Tradeoff

Often you can trade time for space or vice versa:

// Approach 1: O(n) time, O(1) space
// Find duplicate by checking all pairs
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] == arr[j]) return true;
    }
}

// Approach 2: O(n) time, O(n) space
// Find duplicate using HashSet
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
    if (!seen.add(num)) return true;
}

Both are O(n) time, but the second uses O(n) extra space.

Big O describes the upper bound of an algorithm's growth rate.

Formal Definition

f(n) is O(g(n)) if there exist positive constants c and n₀ such that:

f(n) ≤ c × g(n) for all n ≥ n₀

In Plain English

"The algorithm's runtime grows at most as fast as g(n)."

Examples

O(n) means at most linear:

// This is O(n)
for (int i = 0; i < n; i++) {
    // constant work
}
// Even if we do 2n operations:
for (int i = 0; i < n; i++) {
    a(); // constant
    b(); // constant
}
// Still O(n) because 2n ≤ c×n for c=2

O(n²) means at most quadratic:

// This is O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // constant work
    }
}

Dropping Constants

We always drop constants and lower-order terms:

Actual Operations	Big O
5	O(1)
3n + 100	O(n)
2n² + 5n + 10	O(n²)
n³/3 + n²	O(n³)
log₂(n) + 10	O(log n)

Why Drop Constants?

Because for large enough n, constants don't matter:

• 100n vs n²: At n=100, they're equal. For n>100, n² is worse
• 1000n vs n²: At n=1000, they're equal. For n>1000, n² is worse

The crossover point exists, but we care about asymptotic behavior (as n approaches infinity).

Rules for Big O

1. Sum Rule: O(f(n) + g(n)) = O(max(f(n), g(n)))
2. Product Rule: O(f(n) × g(n)) = O(f(n) × g(n))
3. Constant Rule: O(c × f(n)) = O(f(n))
4. Log Rule: O(log_a(n)) = O(log_b(n)) for any a,b > 1

Big Theta (Θ) describes the tight bound of an algorithm's growth rate.

Formal Definition

f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:

c₁ × g(n) ≤ f(n) ≤ c₂ × g(n) for all n ≥ n₀

In Plain English

"The algorithm's runtime grows exactly as fast as g(n)."

Why Big Theta Matters

Big O gives an upper bound. But sometimes we want to know the exact growth rate.

Example:

// This loop always runs exactly n times
for (int i = 0; i < n; i++) {
    System.out.println(i);
}

• O(n): Correct (upper bound)
• O(n²): Also correct (upper bound, but loose)
• Θ(n): Precise (tight bound)

When to Use Which

Notation	Use When
O	You want to prove an upper bound
Θ	You want to state exact growth rate
Ω	You want to state a lower bound

In Interviews

Amazon interviewers typically accept Big O for all discussions. But understanding Θ helps you:

1. Know when an algorithm is optimally efficient
2. Understand that some algorithms must take a certain time
3. Recognize when you cannot do better

Example: Merge Sort

Merge Sort always divides the array in half and merges:

T(n) = 2T(n/2) + n

This solves to Θ(n log n).

This means Merge Sort always takes n log n time—not just on average, not just in the best case, but always.

Comparison with Big O

Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	Θ(n)	Θ(n²)	Θ(n²)
Merge Sort	Θ(n log n)	Θ(n log n)	Θ(n log n)
Quick Sort	Θ(n log n)	Θ(n log n)	Θ(n²)

Merge Sort is Θ(n log n) in all cases. Quick Sort is only Θ(n log n) on average.

Big Omega (Ω) describes the lower bound of an algorithm's growth rate.

Formal Definition

f(n) is Ω(g(n)) if there exist positive constants c and n₀ such that:

f(n) ≥ c × g(n) for all n ≥ n₀

In Plain English

"The algorithm's runtime grows at least as fast as g(n)."

Why Big Omega Matters

Sometimes we want to prove that an algorithm cannot be faster than a certain rate.

Example: Searching an unsorted array

// Must check each element at least once
for (int i = 0; i < n; i++) {
    if (arr[i] == target) return i;
}
// This is Ω(n) - you MUST look at each element

You cannot search an unsorted array faster than O(n). This is a proven lower bound.

Lower Bounds in Practice

Problem	Lower Bound	Why
Search unsorted array	Ω(n)	Must check each element
Sort n elements	Ω(n log n)	Comparison-based sorting
Matrix multiplication	Ω(n²)	Must read all elements
Find max in array	Ω(n)	Must check each element

Interview Relevance

When an interviewer asks: "Can you do better?"

If you can prove the problem has a Ω(n log n) lower bound, and your algorithm is O(n log n), you've found the optimal solution.

Example conversation:

• Interviewer: "Can you sort this faster than O(n log n)?"
• You: "For comparison-based sorting, O(n log n) is the theoretical lower bound. We can only do better with non-comparison sorts like Counting Sort, which have their own constraints."

This demonstrates deep understanding.

Growth Rate Visualization

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
1	1	0	1	0	1	2
10	1	3.3	10	33	100	1,024
100	1	6.6	100	664	10,000	10³⁰
1,000	1	10	1,000	9,966	1,000,000	10³⁰¹
10,000	1	13.3	10,000	132,877	100,000,000	10³⁰¹⁰
100,000	1	16.6	100,000	1,660,964	10¹⁰	10³⁰¹⁰³

Key Observations

1. O(1) is always fast, regardless of n
2. O(log n) grows extremely slowly (binary search)
3. O(n) is linear—directly proportional
4. O(n log n) is slightly worse than O(n) (sorting)
5. O(n²) becomes impractical quickly
6. O(2ⁿ) is completely impractical for n > 30

When Each Complexity is Acceptable

Complexity	Max n in 1 second	Typical Use
O(1)	Any	Direct access
O(log n)	10¹⁸	Binary search
O(n)	10⁸	Single pass
O(n log n)	10⁷	Sorting
O(n²)	5,000	Brute force
O(n³)	300	Matrix operations
O(2ⁿ)	20	Subset enumeration
O(n!)	10	Permutations

Interview Rule of Thumb

For Amazon OA (Online Assessment):

• 1 second = ~10⁸ operations
• If n ≤ 100, O(n³) is acceptable
• If n ≤ 1,000, O(n²) is acceptable
• If n ≤ 100,000, O(n log n) is acceptable
• If n ≤ 10,000,000, O(n) is acceptable

The Amazon Interview Process

Amazon SDE-1 interviews typically include:

1. Online Assessment (OA): 2 coding problems in 70 minutes
2. Technical Interviews (2-3 rounds): 1-2 problems each
3. Behavioral Interview: Leadership Principles

Complexity Expectations

Round	Expected Complexity	Why
OA	O(n log n) or better	Must pass automated tests
Technical	O(n) or O(n log n)	Shows optimization skills
Follow-up	Best possible	Demonstrates depth

How to Discuss Complexity

Step 1: State your approach
"I'll use a HashMap to store frequencies, which allows O(1) lookup."

Step 2: Analyze time
"I iterate through the array once: O(n). Then I iterate through the map: O(n). Total: O(n)."

Step 3: Analyze space
"I use a HashMap that stores at most n elements: O(n) space."

Step 4: Discuss optimization
"We could reduce space to O(1) by sorting first, but that would increase time to O(n log n)."

Common Follow-Up Questions

1. "Can you do better?" - Discuss lower bounds
2. "What about space?" - Analyze space complexity
3. "What if the input is sorted?" - Use that information
4. "What about edge cases?" - Empty, single element, all same

Red Flags to Avoid

1. Not analyzing complexity: Always state it
2. Wrong analysis: Double-check your math
3. Ignoring space: Interviewers care about both
4. Not discussing tradeoffs: Show you understand alternatives

Mistake 1: Counting Constants

Wrong: "This loop does 2n operations, so it's O(2n)"
Correct: "This loop does 2n operations, so it's O(n)"

Constants are always dropped.

Mistake 2: Ignoring Dominant Term

Wrong: "This code does n² + n operations, so it's O(n² + n)"
Correct: "This code does n² + n operations, so it's O(n²)"

Only the dominant term matters.

Mistake 3: Confusing Input Size

Wrong: Analyzing array size when the key variable is different
Correct: Identify what actually affects runtime

// What's the input size?
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // O(n × m), not O(n²)
    }
}

Mistake 4: Forgetting Recursion

Wrong: "This recursive function looks simple, so it's O(n)"
Correct: Analyze the recursion tree

// This is O(2ⁿ), not O(n)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Mistake 5: Assuming Best Case

Wrong: "This sort is O(n) because the input might already be sorted"
Correct: Analyze worst case unless specified

Mistake 6: Mixing Time and Space

Wrong: "This algorithm is O(n)" (without specifying time or space)
Correct: "This algorithm is O(n) time and O(1) space"

Quick Self-Check

Before stating complexity, ask:

1. Am I analyzing time or space?
2. What is the input size?
3. What is the dominant operation?
4. Am I dropping constants?
5. Am I considering worst case?