Introduction to Big O Notation

# CHAPTER 1

Introduction to Big O Notation #

Two functions that search a list of a million items, timed on the same machine:

Linear search    ~1,000,000 comparisons    about 50 ms
Binary search             20 comparisons    about 0.002 ms

Both are correct. Both return the same answer. One is roughly twenty-five thousand times faster, and the gap widens as the list grows — at a billion items linear search needs a billion comparisons while binary search needs thirty.

Big O notation is how we describe that difference without benchmarking anything. It answers one specific question: as the input grows, how does the amount of work grow with it? Linear search is O(n) — double the data, double the work. Binary search is O(log n) — double the data, and the work increases by a single step.

Notice what the notation deliberately discards. It ignores constant factors, hardware, and programming language, because those change and the growth rate does not. An O(n²) algorithm written in hand-optimised C on a fast machine will still lose to an O(n log n) algorithm in Python once the input is large enough. Big O tells you where that crossover is inevitable.

This is the vocabulary technical interviews are conducted in, but the practical value outlasts the interview: it is how you tell, before writing any code, which of two approaches will still work when your data is a hundred times larger than it is today.

We begin with growth rates and the intuition behind the notation, then make it formal.

1. What is Big O Notation? #

We do not use Big O to count the *exact* number of operations. We use it to describe the Trend or Rate of Growth.

• If doubling the input size doubles the work, that is a linear trend: $O(n)$.

• If doubling the input size quadruples the work, that is a quadratic trend: $O(n^2)$.

2. Why Not Measure in Seconds? #

1. 1. Hardware Dependency: Your code might run in 0.05s on a massive $5000 gaming PC, but take 10 seconds on a cheap smartphone.

1. 2. Background Processes: The CPU might be running an antivirus scan in the background during the test, skewing the results.

1. 3. Language Differences: C++ is natively faster than Python. We need a way to evaluate the *logic* of the algorithm itself, independent of the programming language.

Big O solves this. It measures the *Number of Operations*, not the physical time. Hardware doesn't matter.

3. The Concept of Input Size ($n$) #

• If you are searching through an array of 500 names, $n = 500$.

• If you are processing a string of 10,000 characters, $n = 10,000$.

4. Visualizing Growth Rates #

Input Size (n)

O(1)      → Constant (The absolute fastest)
O(log n)  → Logarithmic (Extremely Fast)
O(n)      → Linear (Fast and proportional)
O(n log n)→ Linearithmic (Decent, standard for sorting)
O(n²)     → Quadratic (Slow, dangerous for large inputs)
O(2ⁿ)     → Exponential (Catastrophic for large inputs)
O(n!)     → Factorial (The absolute worst)

5. Code Example: Constant vs Linear #

#### C Example

#include <stdio.h>

// Example 1: O(1) Constant Time.
// No matter how big 'n' is, this always takes exactly 1 operation.
void printFirstItem(int arr[], int n) {
    printf("%d\n", arr[0]); 
}

// Example 2: O(n) Linear Time.
// If 'n' is 100, the loop runs 100 times. If 'n' is 1000, it runs 1000 times.
void printAllItems(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[i]);
    }
}

#### Python Example

# Example 1: O(1) Constant Time
def print_first_item(arr):
    print(arr[0])

# Example 2: O(n) Linear Time
def print_all_items(arr):
    for item in arr:
        print(item)

#### Java Example

public class Complexity {
    // O(1) Constant Time
    public void printFirst(int[] arr) {
        System.out.println(arr[0]);
    }

    // O(n) Linear Time
    public void printAll(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

#### C++ Example

#include <iostream>
using namespace std;

// O(1) Constant Time
void printFirst(int arr[]) {
    cout << arr[0] << endl;
}

// O(n) Linear Time
void printAll(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << endl;
    }
}

6. Complexity Breakdown Table #

7. Common Mistakes #

• Confusing Time with Operations: Beginners often think Big O measures physical seconds. It does not. It strictly measures the theoretical growth of mathematical operations as the input approaches infinity.

• Worrying about small inputs: For an array of 5 items, $O(n^2)$ and $O(1)$ execute in essentially the exact same time (0.0001ms). Big O only matters when $n$ becomes massive.

8. Optimization Tips #

• Always identify $n$ first: Before you can optimize code, you must define exactly what your input variable is. Is it the length of an array? The height of a tree?

• Avoid Nested Loops: The easiest way to accidentally create a slow $O(n^2)$ algorithm is to place a for loop inside another for loop.

9. Exercises #

1. 1. If an algorithm takes 10 operations to process 10 items, and 100 operations to process 100 items, what is its likely Big O notation?

1. 2. Why is measuring algorithm efficiency using a stopwatch on your personal laptop fundamentally flawed?

10. MCQs with Answers #

11. Interview Preparation #

• *Conceptual Defense:* "An interviewer asks: Why don't we just buy faster servers instead of worrying about Big O?" *(Answer: Hardware has physical limits. If an algorithm is $O(2^n)$, adding an input size of just $n=100$ results in more operations than there are atoms in the universe. No amount of hardware money can solve bad math).*

12. FAQs #

13. Summary #

14. Next Chapter Recommendation #