Understanding T(n), f(n), and the Real Reason Behind Big-O

“Don’t just learn the formulas. Learn why mathematicians invented them.” 💡

---

📖 Quick Recap of Part 1

In Part 1, we discovered that Asymptotic Notation is not about measuring the exact running time of an algorithm.

Instead, it studies how the running time grows as the input size becomes extremely large.

We also learned an important concept.

Whenever we count the exact number of operations performed by an algorithm, we represent it as$$\boxed{T(n)}$$T(n)​

For example,

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

After counting all the operations, we obtained$$T(n)=3n+2$$T(n)=3n+2

This is called the Running-Time Function.

At this point, everything seems perfect.

We know exactly how many operations our algorithm performs.

So, a very interesting question arises…

---

🤔 If We Already Know T(n), Why Do We Need Another Function?

Imagine your teacher asks:

“What is the running time of your algorithm?”

You confidently answer:$$T(n)=3n+2$$T(n)=3n+2

The teacher smiles and asks another question.

“Can you compare your algorithm with another algorithm?”

Suppose another student writes a different algorithm whose running time is$$T(n)=5n+100$$T(n)=5n+100

Now both of you have exact running-time functions.

But comparing them directly is not very convenient.

Why?

Because every algorithm will have a different mathematical expression.

For example,

Algorithm A$$T(n)=3n+2$$T(n)=3n+2

Algorithm B$$T(n)=5n+100$$T(n)=5n+100

Algorithm C$$T(n)=7n+20$$T(n)=7n+20

Algorithm D$$T(n)=100n+500$$T(n)=100n+500

Imagine comparing thousands of algorithms using their exact running-time equations!

It quickly becomes complicated.

Computer Scientists wanted something simpler.

Instead of comparing exact equations,

they wanted to compare growth patterns.

And that is why they introduced another function called$$\boxed{f(n)}$$f(n)​

---

🤔 What is f(n)?

This is one of the most misunderstood concepts in DSA.

Many students think

f(n) is the running time.

This is incorrect.

Let’s understand the difference.

T(n)

represents

The exact running-time function of an algorithm.

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

---

f(n)

represents

A simpler function that captures the growth pattern of T(n).

For the above example,

the dominant term is$$n$$n

Therefore,

we choose$$\boxed{f(n)=n}$$f(n)=n​

Notice the wording.

We did not calculate f(n).

We selected it.

This is a very important distinction.

---

🎯 T(n) is Calculated, f(n) is Chosen

Let’s understand this carefully.

Suppose we analyze a Java program.

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

After counting every operation,

we obtain$$T(n)=3n+2$$T(n)=3n+2

This value comes from mathematics.

We actually counted

• Initialization
• Condition
• Increment
• Loop Body

Therefore,$$T(n)$$T(n)

is calculated.

Now we ask another question.

What is the dominant growth of this function?

The answer is$$n$$n

Therefore,

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

Notice that nobody counted operations to obtain$$f(n)$$f(n)

It is simply chosen because it represents the overall growth.

---

📌 Example 1

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

The terms are

• $3n$3n
• $2$2

Which term grows faster?

Obviously,$$3n$$3n

Ignoring the constant,

we get$$n$$n

Therefore,$$\boxed{f(n)=n}$$f(n)=n​

---

📌 Example 2

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

Which term grows the fastest?

Clearly,$$5n^2$$5n2

Ignoring the constant coefficient,

we obtain$$n^2$$n2

Therefore,$$\boxed{f(n)=n^2}$$f(n)=n2​

---

📌 Example 3

Suppose$$T(n)=8\log n+100$$T(n)=8logn+100

The dominant term is$$\log n$$logn

Therefore,$$\boxed{f(n)=\log n}$$f(n)=logn​

---

📌 Example 4

Suppose$$T(n)=4\sqrt n+25$$T(n)=4n​+25

The dominant term is$$\sqrt n$$n​

Therefore,$$\boxed{f(n)=\sqrt n}$$f(n)=n​​

---

📊 T(n) vs f(n)

This is probably the most important table in this entire chapter.

T(n)	f(n)
Exact running-time function	Simplified growth function
Obtained by counting operations	Chosen by observing the dominant growth
Includes constants	Ignores constant factors
Includes lower-order terms	Keeps only the dominant term
Different for every algorithm	Used to classify algorithms into growth categories

---

🎯 Understanding the Difference Through an Example

Suppose you own a car.

Every day you drive different distances.

Monday

51 km

Tuesday

49 km

Wednesday

53 km

Thursday

50 km

Friday

52 km

These are your exact daily distances.

Think of them as$$T(n)$$T(n)

Now suppose someone asks

“How much do you usually travel?”

You don’t answer

51 km
49 km
53 km
50 km
52 km

Instead,

you simply say

Around 50 km every day.

That simplified description is like$$f(n)$$f(n)

Notice something.

The exact values still exist.

But for understanding the overall pattern,

the simplified value is much more useful.

That is exactly why mathematicians introduced$$f(n)$$f(n)

---

🚗 Another Real-Life Analogy

Suppose two people earn salaries.

Person A

₹59,850

Person B

₹60,200

When someone asks,

“How much do they earn?”

Most people answer

Around ₹60,000 per month.

Why?

Because

• ₹59,850
• ₹60,200

both represent approximately the same scale.

Similarly,$$3n+2$$3n+2

and$$5n+100$$5n+100

both belong to the same growth category$$n$$n

---

🤔 Why Can’t We Simply Use T(n)?

This is an excellent question.

Suppose someone invents ten different algorithms.

Their running times are$$3n+2$$3n+2 $$5n+100$$5n+100 $$7n+20$$7n+20 $$10n+500$$10n+500 $$100n+1000$$100n+1000

Although all these expressions are different,

their growth is identical.

Every one of them grows linearly.

Instead of remembering five different equations,

it is much easier to classify them into one category.

That category is$$\boxed{n}$$n​

This is the purpose of$$f(n)$$f(n)

It acts as a classification function.

---

💡 Think of f(n) as a Category

Imagine a classroom.

Students have different heights.

171 cm

174 cm

176 cm

179 cm

181 cm

Instead of remembering every height,

we classify them as

Tall Students

Similarly,

instead of remembering$$3n+2$$3n+2 $$5n+100$$5n+100 $$100n+50$$100n+50

we classify them as$$O(n)$$O(n)

Notice that

we are no longer interested in the exact equation.

We are only interested in the growth category.

---

⚠️ Common Mistake

Many beginners think

T(n) and f(n) are the same thing.

They are not.

Remember this carefully.$$T(n)$$T(n)

is

The exact running-time function.

Whereas$$f(n)$$f(n)

is

A simplified function used for comparison and classification.

---

🧠 Memory Trick

Whenever you see$$T(n)$$T(n)

think

True Running Time

Whenever you see$$f(n)$$f(n)

think

Final Growth Pattern

Although this isn’t the official meaning of the letters, it’s a useful memory aid for beginners.

---

🎯 Key Takeaways

By now, you should understand:

✅ T(n) is the exact running-time function obtained by counting operations.

✅ f(n) is a simplified function that represents the dominant growth of T(n).

✅ T(n) is calculated.

✅ f(n) is chosen.

✅ T(n) tells us the exact running time.

✅ f(n) helps classify algorithms into growth categories.

---

📌 Coming Up Next (Part 2B)

Now that we understand the difference between T(n) and f(n), the next logical question is:

🤔 If we already have T(n), why do we ignore constants?

🤔 Why do we ignore lower-order terms?

🤔 Why is only the dominant term important?

We’ll answer these questions with detailed numerical examples, intuitive analogies, and the mathematical reasoning behind them. Finally, we’ll introduce the famous formula:$$0 \le T(n) \le c \cdot f(n)$$0≤T(n)≤c⋅f(n)

and explain why mathematicians compare T(n) with f(n) before we dive into its full proof in Part 3.