Before diving into Big O notation, it’s important to understand why we study it and how it connects to real-world coding problems.

1. Why Study Big O Notation?

There are three key reasons why understanding complexity analysis and Big O notation is crucial.

Reason 1 — Essential for Coding Interviews

In technical interviews, after solving a problem, you’ll almost always be asked:

“What’s the time complexity of your solution?”

Even if your algorithm works perfectly, if you can’t analyze its complexity, it signals to the interviewer that you may not be able to assess performance in real-world scenarios. Since Big O notation is the standard way to express algorithm efficiency, not knowing it can cost you the job.

Reason 2 — Preventing Performance Loss

Misunderstanding complexity can lead to algorithms that are unnecessarily slow, especially as input sizes grow.
For example, an algorithm that works fine for 1,000 elements might take hours for 10 million elements if its complexity is inefficient.

Reason 3 — Identifying and Fixing Inefficient Code

When you understand complexity, you can spot inefficiencies in existing code and refactor them into faster, more scalable solutions.

2. Starting with the Basics: Functions in Mathematics

Before we explain Big O, we need to revisit a concept from mathematics: functions.

A function defines a relationship between input(s) and output, following a rule.

Example:

y=x+1

This means that:

• y depends on x
• If x changes, y changes according to the rule: add 1.

Formally:

A function is a mathematical object that, when given an input, produces an output according to a predefined rule (often described by a formula).

We write functions like:

• f(x)
• g(n,k)
• or any name with arguments.

Example:

g(n,k)=(n+k)/2​

This function returns the average of n and k.

Function Example in Real Life

Let’s make this more tangible.

Scenario:
You need to send a file to a friend who lives 600 miles away.

Option 1 — Send Over the Internet

• Works well for small files.
• But if the file is hundreds of terabytes, the transfer could take weeks.

Option 2 — Send by Plane

• Load hard drives onto a plane.
• Travel time is fixed — file size won’t change the speed.

3. Describing Dependencies with Functions

Functions can represent dependencies between variables.

In our file transfer example:

• Variable 1: File size (N bytes)
• Variable 2: Transfer time

We can define a function:

F(N)=transfer time based on size N

Case 1 — Network Transfer

• The more bytes, the longer it takes.
• Transfer time increases proportionally with file size:
  F₁​(N)=N

Graph:

• X-axis: File size
• Y-axis: Time
• Straight line going upward.

Case 2 — Airplane Transfer

Plane speed is constant.

File size has almost no effect on travel time:

F₂​(N)=1

Graph:

• X-axis: File size
• Y-axis: Time
• Flat horizontal line.

4. Connecting to Algorithm Complexity

The same principle applies to algorithms:

• The input size is like the file size.
• The runtime is like the transfer time.
• The relationship between them is the complexity.

Big O notation is simply a standardized way to describe how runtime (or memory usage) changes as input size grows.

From here, we can start analyzing algorithms using the same thinking we applied to file transfer.