“Don’t memorize Time Complexity—understand how the code executes.”

---

📖 Introduction

If you’re learning Data Structures and Algorithms (DSA), one of the first topics you’ll encounter is Time Complexity. It is one of the most important concepts for technical interviews, coding competitions, university exams, and software development.

However, many beginners approach Time Complexity the wrong way. They simply memorize statements like:

• One loop → O(n)
• Two nested loops → O(n²)
• Binary Search → O(log n)

But if an interviewer slightly changes the code, many students get confused because they never learned how to calculate Time Complexity.

For example:

• Why is i = i + 2 still O(n)?
• Why is i = i * 2 O(log n)?
• Why is i * 2 < n not logarithmic?
• Why do we ignore constants like 3n + 2?

If you’ve ever asked yourself these questions, this guide is for you.

Instead of memorizing formulas, we’ll learn how to analyze Java programs step by step.

By the end of this series, you’ll be able to calculate the Time Complexity of most loop-based programs with confidence.

---

🎯 Why Should You Learn Time Complexity?

Imagine you write two Java programs that solve the same problem.

Program A

Takes 1 second to process 1,000 records.

Program B

Takes 20 seconds to process the same 1,000 records.

Both programs produce the same output.

Which one would you choose?

Obviously, Program A.

Now imagine the input size becomes 1 million instead of 1,000.

The difference becomes enormous.

This is why software engineers don’t just ask:

“Does the program work?”

They also ask:

“How efficiently does it work?”

That’s exactly what Time Complexity helps us measure.

---

🤔 What is Time Complexity?

Time Complexity measures how the running time of an algorithm grows as the input size (n) increases.

Notice the wording carefully.

It does not measure:

❌ Execution time in seconds

❌ CPU speed

❌ RAM usage

❌ Programming language speed

Instead, it measures the growth rate of an algorithm.

---

Example

Consider these two Java programs.

Program A

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

---

Program B

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

The second program executes approximately 100 times more operations.

Yet both programs are classified as

O(n)

Why?

Because both algorithms grow linearly as the input size increases.

---

📈 What is Big-O Notation?

Whenever we talk about Time Complexity, we use Big-O notation.

The “O” stands for

Order of Growth

Big-O describes how the running time grows as the input size becomes very large.

It focuses on the overall growth pattern, not the exact number of operations.

---

🤔 Why is it Called “Big-O”?

Many students wonder why we call it Big-O.

The answer comes from mathematics.

Mathematicians use several symbols to describe the growth of functions.

Notation	Meaning
Big O (O)	Upper bound (worst-case growth)
Big Omega (Ω)	Lower bound (best-case growth)
Big Theta (Θ)	Tight bound (exact asymptotic growth)

In programming, we mostly use Big-O because it helps us describe how an algorithm behaves in the worst case.

---

✂️ Why Do We Ignore Constants?

Suppose one algorithm performs

3n + 2

operations.

Another performs

100n + 500

operations.

Clearly, the second algorithm performs much more work.

However, both algorithms still grow linearly.

Therefore,

3n + 2

becomes

O(n)

Similarly,

25n² + 100n + 50

becomes

O(n²)

because the n² term dominates as the input becomes very large.

---

💡 Think of It This Way

Imagine two cars.

🚗 Car A travels at 60 km/h.

🏎️ Car B travels at 120 km/h.

Car B is twice as fast.

But both cars still travel at a constant speed.

Their speeds are different.

Their growth pattern is the same.

Big-O focuses on the growth pattern, not the constant difference.

---

📚 Rules for Calculating Time Complexity

Before solving any problem, remember these simple rules.

---

✅ Rule 1 — Count the Repeating Statement

We count the number of times the important statement executes.

For example,

sum = sum + arr[i];

or

System.out.println(i);

These are called constant-time operations.

---

✅ Rule 2 — Break Every for Loop into Four Parts

Every Java for loop has four components.

for(initialization; condition; increment)
{
    // body
}

We analyze each separately.

1️⃣ Initialization

2️⃣ Condition

3️⃣ Increment (or Decrement)

4️⃣ Loop Body

---

Understanding the Four Parts of a Loop

Consider this simple loop.

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

Let’s analyze it carefully.

---

Step 1 — Initialization

int i = 0;

Runs only once.

Operations

1

---

Step 2 — Condition

i < n

This condition executes before every iteration.

It also executes one extra time when it finally becomes false.

Therefore,

Condition executes

n + 1

times.

---

Why?

Suppose

n = 5

The condition is checked like this.

i = 0 ✔

i = 1 ✔

i = 2 ✔

i = 3 ✔

i = 4 ✔

i = 5 ✘

Notice the final false condition is also checked.

This is why we always count

n + 1

condition checks.

---

Step 3 — Increment

i++

Runs after every successful iteration.

Operations

n

---

Step 4 — Loop Body

System.out.println(i);

Runs

n

times.

---

Total Operations

Initialization

1

+

Condition

(n + 1)

+

Increment

n

+

Body

n

Total

3n + 2

Ignoring constants,

Final Answer

✅ O(n)

---

✅ Example 1 — Simple Linear Loop

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

Analysis

Initialization

1

Condition

n + 1

Increment

n

Body

n

Total

3n + 2

Ignoring constants,

✅ Time Complexity = O(n)

---

📌 Key Observation

A loop that increments by 1 executes approximately n times.

Therefore,

i++

usually results in

O(n)

---

✅ Example 2 — Two Statements Inside the Loop

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

Here the loop body contains two constant-time statements.

Initialization

1

Condition

n + 1

Increment

n

Loop Body

2n

Total

1

+

(n + 1)

+

n

+

2n

=

4n + 2

Ignoring constants,

✅ Time Complexity = O(n)

---

💡 Interview Tip

Many students think that adding more statements changes the complexity.

It doesn’t.

Whether there are 2, 5, or 100 constant-time statements inside the loop,

the complexity remains

O(n)

because constants are ignored.

---

✅ Example 3 — Increment by 2

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

---

Dry Run

The values of i become

1

3

5

7

9

...

The loop skips every alternate number.

Therefore,

the number of iterations is approximately

n / 2

---

Operation Count

Initialization

1

Condition

(n/2) + 1

Increment

n/2

Loop Body

n/2

Total

1

+

(n/2 + 1)

+

n/2

+

n/2

=

3n/2 + 2

Ignoring constants,

✅ Time Complexity = O(n)

---

📌 Key Observation

Although the loop executes only half as many times,

Big-O ignores constant factors.

Therefore,

O(n/2)

becomes

O(n)

---

✅ Example 4 — Increment by 3

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

---

Dry Run

Values become

1

4

7

10

13

...

The loop executes approximately

n / 3

times.

---

Operation Count

Initialization

1

Condition

(n/3) + 1

Increment

n/3

Loop Body

n/3

Total

1

+

(n/3 + 1)

+

n/3

+

n/3

=

n + 2

Ignoring constants,

✅ Time Complexity = O(n)

---

🚀 Memory Trick

Whenever the loop variable changes by a fixed constant, such as

i++

i += 2

i += 3

i += 10

or

i -= 5

the Time Complexity remains

O(n)

because the number of iterations is always proportional to n.

---

📝 Part 1 Summary

In this part, we learned:

✅ What Time Complexity is

✅ Why Time Complexity is important

✅ What Big-O notation means

✅ Why it is called Big-O

✅ Why constants are ignored

✅ How to analyze the four parts of a for loop

✅ How to calculate Time Complexity step by step

✅ Why i++, i += 2, and i += 3 all have O(n) complexity

---

📌 Coming Up in Part 2

In the next part, we’ll explore more interesting examples, including:

• ✅ i = i - 2
• ✅ Why i * 2 < n is O(n) (not O(log n))
• ✅ Understanding logarithms from scratch
• ✅ i = i * 2
• ✅ i = i / 2
• ✅ O(√n) with a complete Prime Number example
• ✅ Nested loops and O(n²)

By the end of Part 2, you’ll understand why logarithmic algorithms are so efficient and how to identify them instantly.