Welcome to the final part of this guide! 🎉

In Part 1, we learned the fundamentals of Time Complexity, Big-O notation, and how to analyze simple loops.

In Part 2, we explored logarithmic complexity (O(log n)), square root complexity (O(√n)), and learned why multiplying or dividing the loop variable changes the complexity dramatically.

Now, it’s time to understand the most common complexities used in real-world algorithms:

• ✅ O(n²)
• ✅ O(n log n)
• ✅ O(n³)
• ✅ Ordering Big-O notations
• ✅ Common interview mistakes
• ✅ Memory tricks
• ✅ Final revision

Let’s begin!

---

✅ Example 10 – Nested Loops (O(n²))

One of the most common interview questions involves nested loops.

Consider the following program.

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

---

Step 1 – Analyze the Outer Loop

The outer loop is

for(int i = 0; i < n; i++)

From Part 1, we already know that this loop executes

n

times.

---

Step 2 – Analyze the Inner Loop

The inner loop is

for(int j = 0; j < n; j++)

This loop also executes

n

times.

---

Step 3 – Multiply the Iterations

Here’s the important point:

The inner loop runs every time the outer loop executes.

Suppose

n = 4

The execution looks like this.

Outer Loop
↓

i = 0
    j = 0
    j = 1
    j = 2
    j = 3

i = 1
    j = 0
    j = 1
    j = 2
    j = 3

i = 2
    j = 0
    j = 1
    j = 2
    j = 3

i = 3
    j = 0
    j = 1
    j = 2
    j = 3

The inner loop executes

4 × 4 = 16

times.

In general,

n × n

which equals

n²

Therefore,

✅ Time Complexity = O(n²)

---

📌 Memory Rule

Whenever one loop is completely inside another,

👉 Multiply the number of iterations.

---

✅ Example 11 – Triangular Loop

Now consider a slightly different nested loop.

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

Notice something?

The inner loop no longer executes n times.

Instead,

its execution depends on the value of i.

---

Dry Run

Suppose

n = 5

The iterations become

i = 0 → 0 iterations

i = 1 → 1 iteration

i = 2 → 2 iterations

i = 3 → 3 iterations

i = 4 → 4 iterations

Total iterations become

0 + 1 + 2 + 3 + 4

Instead of multiplying,

we now need a summation formula.

---

Summation Formula

The sum

0 + 1 + 2 + ... + (n-1)

is

[
\frac{n(n-1)}{2}
]

Expanding,

[
\frac{n^2-n}{2}
]

Ignoring constants and lower-order terms,

the dominant term is

[
n^2
]

Therefore,

✅ Time Complexity = O(n²)

---

💡 Why Isn’t It O(n)?

Although the inner loop does not always execute n times,

the total number of iterations still grows proportionally to

[
n^2
]

That’s why triangular loops are still O(n²).

---

✅ Example 12 – O(n log n)

This complexity is extremely important because many efficient sorting algorithms use it.

Consider the following code.

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

---

Analyze the Outer Loop

for(int i = 0; i < n; i++)

Runs

n

times.

---

Analyze the Inner Loop

for(int j = 1; j < n; j = j * 2)

This is a logarithmic loop.

It executes

log n

times.

---

Combine Them

Since the logarithmic loop runs for every outer iteration,

Total operations become

n × log n

Therefore,

✅ Time Complexity = O(n log n)

---

🌟 Real-World Examples

Algorithms with O(n log n) complexity include:

• Merge Sort
• Heap Sort
• Average Case of Quick Sort
• Many divide-and-conquer algorithms

These are much faster than quadratic algorithms for large inputs.

---

✅ Example 13 – O(n³)

Consider the following program.

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

---

Analyze the Outer Loop

Runs

n

times.

---

Analyze the Inner Loop

Runs

n²

times.

---

Multiply

n × n²

which equals

n³

Therefore,

✅ Time Complexity = O(n³)

---

📊 Standard Order of Big-O Notations

One of the most frequently asked interview questions is:

Arrange the following Big-O notations from best to worst.

The standard order is:

Rank	Time Complexity	Name
🥇	O(1)	Constant
🥈	O(log n)	Logarithmic
🥉	O(√n)	Square Root
4️⃣	O(n)	Linear
5️⃣	O(n log n)	Linearithmic
6️⃣	O(n²)	Quadratic
7️⃣	O(n³)	Cubic
8️⃣	O(2ⁿ)	Exponential
9️⃣	O(n!)	Factorial

---

🧠 Memory Trick

O(1)

↓

O(log n)

↓

O(√n)

↓

O(n)

↓

O(n log n)

↓

O(n²)

↓

O(n³)

↓

O(2ⁿ)

↓

O(n!)

The higher you are in this list,

the better the algorithm performs as the input grows.

---

📈 Why Does This Order Matter?

Suppose

n = 1,000,000

Approximate number of operations:

Complexity	Approximate Operations
O(1)	1
O(log n)	20
O(√n)	1,000
O(n)	1,000,000
O(n log n)	20,000,000
O(n²)	1,000,000,000,000
O(2ⁿ)	Practically impossible
O(n!)	Astronomically large

This comparison clearly shows why efficient algorithms are so important.

---

⚠️ Common Interview Mistakes

Let’s look at the mistakes students frequently make.

---

❌ Mistake 1

Thinking

i * 2 < n

is logarithmic.

✔ Correct Answer:

O(n)

---

❌ Mistake 2

Confusing

i += 2

with

i *= 2

Remember:

+2 → O(n)

×2 → O(log n)

---

❌ Mistake 3

Forgetting that the condition executes

n + 1

times.

Always count the final false condition.

---

❌ Mistake 4

Not ignoring constants.

For example,

3n + 2

becomes

O(n)

---

❌ Mistake 5

Keeping lower-order terms.

Example

n² + 5n + 100

becomes

O(n²)

---

💡 Golden Rules for Calculating Time Complexity

Whenever you see a program,

follow this checklist.

✅ Step 1

Identify the repeating statement.

---

✅ Step 2

Count the number of iterations.

---

✅ Step 3

Multiply nested loops.

---

✅ Step 4

Use summation formulas for triangular loops.

---

✅ Step 5

Ignore constants.

---

✅ Step 6

Ignore lower-order terms.

---

✅ Step 7

Write the answer using Big-O notation.

---

🧠 Complete Memory Tricks

Constant Increment

i++

i += 2

i += 5

i -= 3

Think

O(n)

---

Multiplication / Division

i *= 2

i *= 3

i /= 2

Think

O(log n)

---

Square Root

i * i <= n

or

Math.sqrt(n)

Think

O(√n)

---

Nested Loops

One loop inside another

↓

Multiply

n × n

↓

O(n²)

---

Triangular Loops

0 + 1 + 2 + ... + (n-1)

↓

Use

[
\frac{n(n-1)}{2}
]

↓

O(n²)

---

📋 Quick Revision Table

Java Loop Pattern	Time Complexity
i++	O(n)
i += 2	O(n)
i += 3	O(n)
i -= 2	O(n)
i * 2 < n	O(n)
i *= 2	O(log n)
i /= 2	O(log n)
i * i <= n	O(√n)
Two Nested Loops	O(n²)
Triangular Loop	O(n²)
Nested Logarithmic Loop	O(n log n)
Loop up to n*n	O(n³)

---

🎯 Final Thoughts

Congratulations! 🎉

You have now completed one of the most important topics in Data Structures and Algorithms.

Let’s quickly recap the journey.

In Part 1, you learned:

• ✅ What Time Complexity is
• ✅ What Big-O notation means
• ✅ Why constants are ignored
• ✅ How to analyze simple loops

In Part 2, you learned:

• ✅ Constant increment vs. multiplication
• ✅ Logarithms from scratch
• ✅ Logarithmic loops
• ✅ Square root complexity
• ✅ Prime number optimization

In Part 3, you learned:

• ✅ Nested loops
• ✅ Triangular loops
• ✅ O(n log n)
• ✅ O(n³)
• ✅ Big-O ordering
• ✅ Interview mistakes
• ✅ Memory tricks

---

🚀 The Most Important Lesson

Don’t try to memorize:

• One loop → O(n)
• Nested loop → O(n²)
• Binary Search → O(log n)

Instead, always ask yourself these questions:

1. How many times does the loop execute?
2. How does the loop variable change?
3. Do I multiply iterations or add them?
4. Can I simplify the mathematical expression?

If you answer these questions correctly, you can calculate the Time Complexity of almost any loop-based program.

---

🌟 What’s Next?

Now that you’ve mastered Time Complexity, you’re ready to move on to more advanced DSA topics, such as:

• 🔍 Binary Search
• 📦 Arrays and Strings
• 🔗 Linked Lists
• 📚 Stacks and Queues
• 🌳 Trees
• 🌐 Graphs
• ⚡ Recursion
• 🧩 Dynamic Programming
• 🔄 Sorting Algorithms

Remember:

Great programmers don’t memorize algorithms—they understand how algorithms work.

Keep practicing, analyze every loop you write, and soon calculating Time Complexity will become second nature.

Happy Coding! 🚀💻