Understanding the Mathematics Behind Big-O

“The mathematical definition is not used to calculate Big-O. It is used to prove that your Big-O answer is correct.” 💡

---

📖 Introduction

Congratulations! 🎉

In Part 1, we learned:

• What Asymptotic Notation is
• Why it was invented
• What T(n) represents

In Part 2, we learned:

• What f(n) represents
• Why we ignore constants
• Why we ignore lower-order terms
• Why we keep only the dominant term

By now, you already know how to determine the Big-O notation of most algorithms.

For example,

Suppose the running time of an algorithm is$$T(n)=3n+2$$

We immediately write$$O(n)$$O(n)

Similarly,$$5n^2+7n+20$$

becomes$$O(n^2)$$O(n2)

Everything looks simple.

But suppose a mathematician asks you a question.

“How do you know that 3n + 2 is actually O(n)?”

Can you prove it?

Simply saying

“Because we ignore constants.”

is not a mathematical proof.

Mathematicians need evidence.

That evidence is provided by one of the most famous formulas in Computer Science.$$\boxed{0\le T(n)\le c\cdot f(n)\qquad \text{for all } n\ge n_0}$$

At first glance, this formula looks scary.

It contains symbols like

• T(n)
• f(n)
• c
• n₀

Most students memorize it without understanding it.

In this article, we are going to understand every single symbol and, more importantly,

why this formula even exists.

---

🤔 Why Was This Formula Invented?

Let’s begin with a simple example.

Suppose you analyzed a Java program.

for(int i = 0; i < n; i++)
{
    System.out.println(i);
}

After counting every operation,

you obtained$$T(n)=3n+2$$T(n)=3n+2

You also know that$$f(n)=n$$f(n)=n

because n is the dominant term.

Now you confidently say

The algorithm is O(n).

A mathematician asks

How do you know?

You reply

Because my teacher told me to ignore constants.

The mathematician smiles and says

“That is not a proof.”

He wants mathematical evidence.

That is exactly why the definition was invented.

It provides a formal mathematical proof that your answer is correct.

---

📌 Understanding Every Symbol

Let’s read the formula carefully.$$0\le T(n)\le c\cdot f(n)\qquad\text{for all }n\ge n_0$$

Instead of trying to understand the whole equation,

let’s understand it one symbol at a time.

---

Step 1 – What Does

$$0\le T(n)$$

Mean?

This is actually the easiest part.

It simply says

The running time of an algorithm can never be negative.

Can an algorithm perform

-50 operations?

No.

Can an algorithm take

-10 seconds?

Again,

No.

Running time is always positive (or zero in a trivial case).

Therefore,$$T(n)\ge0$$T(n)≥0

This part exists simply to make the mathematical definition complete.

---

Step 2 – Understanding

$$T(n)\le c\cdot f(n)$$

This is the most important part of the definition.

It says

The actual running time of the algorithm must never grow faster than a constant multiple of the comparison function.

Notice something very important.

The formula does not say$$T(n)\le f(n)$$

Instead,

it says$$T(n)\le c\cdot f(n)$$

That small constant$$c$$c

changes everything.

---

Step 3 – Substitute the Values

Suppose$$T(n)=3n+2$$T(n)=3n+2

and$$f(n)=n$$f(n)=n

Substituting these into the formula gives$$3n+2\le c\cdot n$$3n+2≤c⋅n

Now the problem becomes very simple.

We only need to find any positive constant $c$c that makes this inequality true.

---

Step 4 – What is c?

This is one of the biggest misconceptions among students.

Many students think

There must be one correct value of c.

That is not true.

The definition says

There exists a positive constant c.

It does not say

Find the smallest value of c.

As long as one valid value exists,

the proof is complete.

---

Let’s Try c = 3

Substitute it.$$3n+2\le3n$$

Subtract$$3n$$

from both sides.

We get$$2\le0$$

False.

Therefore,

c = 3 does not work.

---

Let’s Try c = 4

Now$$3n+2\le4n$$

Subtract$$3n$$

We obtain$$2\le n$$

This is true whenever$$n\ge2$$

Great!

Therefore,

c = 4 works.

---

Can c = 5 Work?

Let’s check.$$3n+2\le5n$$

Subtract$$3n$$

We get$$2\le2n$$

or$$1\le n$$

Also true.

Therefore,

c = 5 also works.

---

Can c = 100 Work?

Absolutely.$$3n+2\le100n$$

For sufficiently large values of$$n$$

this is always true.

Therefore,

c = 100 also works.

---

🎯 Which Value of c is Correct?

Here is the beautiful part.

They are all correct.

The mathematical definition only says

There exists a positive constant c.

It does not ask us to find the smallest one.

This is why

c is called an arbitrary positive constant.

---

Step 5 – What is n₀?

Now let’s understand the last part of the formula.$$\text{for all }n\ge n_0$$for all n≥n0​

Many beginners wonder

Why don’t we check every value of n?

Let’s test our previous inequality.

Using$$c=4$$

we obtained$$3n+2\le4n$$

Now let’s verify it.

n	3n + 2	4n	Condition
1	5	4	❌ False
2	8	8	✅ True
3	11	12	✅ True
4	14	16	✅ True
5	17	20	✅ True

Notice something interesting.

The inequality fails for$$n=1$$

Does that mean

Big-O is wrong?

No.

Because Asymptotic Analysis never studies

small values.

Remember Part 1.

We are interested in$$n\rightarrow\infty$$

Therefore,

we simply choose$$n_0=2$$

and ignore every value smaller than

---

🎯 Why Do We Ignore Small Values?

Because Asymptotic Analysis studies

the behaviour of an algorithm

when the input becomes extremely large.

Small values are not important.

That is exactly why$$n_0$$​

exists.

---

🤔 Why Do We Ignore Constants?

Now we finally understand the real reason.

Suppose$$T(n)=5n^2+10n+20$$

Why don’t we choose$$f(n)=5n^2$$

Instead,

we choose$$f(n)=n^2$$

Why?

Because the constant

5

can always be absorbed into$$c$$

This is the actual mathematical reason we ignore constants.

Not because a teacher said so.

Not because a textbook told us to.

But because the mathematical definition already allows multiplication by any positive constant c.

---

🎯 The Biggest Secret of Big-O

Most students think

the formula$$0\le T(n)\le c\cdot f(n)$$

is used to calculate Big-O.

That is not true.

We calculate Big-O by

• counting operations,
• obtaining T(n),
• identifying the dominant term,
• choosing f(n).

The mathematical definition is used only to prove that our answer is correct.

---

📌 The Entire Process

1. Write the algorithm.
2. Count all operations.
3. Obtain T(n).
4. Choose the dominant growth f(n).
5. Determine the Big-O notation.
6. If someone asks for proof, use

$$0\le T(n)\le c\cdot f(n)$$0≤T(n)≤c⋅f(n)

to justify your answer mathematically.

---

🎯 Key Takeaways

By now, you should understand that:

• T(n) is the exact running-time function.
• f(n) is the simplified growth function.
• c is any positive constant that makes the inequality true.
• n₀ is the point after which the inequality must always hold.
• The formula is not used to calculate Big-O.
• The formula is used to prove that your Big-O classification is mathematically correct.
• The reason we ignore constants is that they are already accounted for by the constant c in the definition.

---

📝 Test Your Understanding

Question 1

What does T(n) represent?

A. Dominant term

B. Actual running-time function

C. Upper bound

D. Lower bound

✅ Answer: B

---

Question 2

Why do we introduce the constant c?

A. To calculate Big-O

B. To represent the CPU speed

C. To allow a constant multiple of the comparison function

D. To count the number of loops

✅ Answer: C

---

Question 3

True or False?

The value of c must be the smallest possible value.

❌ False

---

Question 4

True or False?

The formula $0 \le T(n) \le c \cdot f(n)$0≤T(n)≤c⋅f(n) is mainly used to prove that a Big-O classification is correct.

✅ True

---

🎉 Final Conclusion

Congratulations! You’ve now reached a level of understanding that many students never achieve.

You no longer have to memorize the Big-O definition. Instead, you understand why it exists, what every symbol means, and how it connects to the process of analyzing algorithms.

The next time you see:$$0 \le T(n) \le c \cdot f(n)$$

you won’t see a complicated mathematical formula.

You’ll see it for what it really is:

A formal mathematical proof that confirms your Big-O answer is correct.