Welcome back! In Part 1, we learned what Time Complexity is, what Big-O notation means, why constants are ignored, and how to analyze simple loops. We also saw why loops with i++, i += 2, and i += 3 all have O(n) time complexity.

In this part, we’ll answer some of the most confusing questions students have:

• 🤔 Is counting backwards different from counting forwards?
• 🤔 Is i * 2 < n logarithmic?
• 🤔 What exactly is a logarithm?
• 🤔 Why does i = i * 2 become O(log n)?
• 🤔 What is O(√n) and where is it used?

Let’s begin!

---

✅ Example 5 – Decrement by 2

Many students think that counting backwards changes the Time Complexity.

Let’s see whether that’s true.

for(int i = n; i > 0; i = i - 2)
{
    System.out.println(i);
}

---

Step 1 – Initialization

int i = n;

Runs only once.

Operations = 1

---

Step 2 – Condition

i > 0

The condition is checked before every iteration and one extra time when it becomes false.

---

Step 3 – Decrement

i = i - 2;

Suppose

n = 10

The values become

10

8

6

4

2

The loop executes

n / 2

times.

---

Step 4 – Loop Body

System.out.println(i);

Also executes

n / 2

times.

---

Total Operations

Initialization

1

Condition

(n/2) + 1

Decrement

n/2

Loop Body

n/2

Total

3n/2 + 2

Ignoring constants,

✅ Time Complexity = O(n)

---

📌 Key Observation

Whether the loop counts:

i++

or

i--

or

i = i - 2

or

i = i + 5

the complexity remains O(n) because the loop variable changes by a constant amount.

---

✅ Example 6 – Is This O(log n)?

This is one of the most common interview questions.

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

Many beginners immediately think:

“There is a 2, so it must be logarithmic.”

❌ Wrong!

Let’s analyze it carefully.

---

Step 1 – Simplify the Condition

The condition is

i × 2 < n

Divide both sides by 2.

i < n / 2

The loop is actually equivalent to

for(int i = 1; i < n/2; i++)

Notice something?

The loop variable still changes like this:

i++

It is not doubling.

---

Dry Run

Suppose

n = 20

The values of i become

1

2

3

4

5

6

7

8

9

When

i = 10

the condition becomes

10 × 2 = 20

which is false.

The loop executes approximately

n/2

times.

Therefore,

✅ Time Complexity = O(n)

---

⚠️ Interview Tip

Always ask yourself:

“What changes the loop variable?”

If the loop variable changes by

i++

or

i += 2

or

i -= 5

the complexity is usually O(n).

Changing the condition does not automatically make the loop logarithmic.

---

🤔 What Exactly is a Logarithm?

Before understanding logarithmic loops, let’s first understand what a logarithm actually means.

Suppose we have

2¹ = 2

2² = 4

2³ = 8

2⁴ = 16

2⁵ = 32

2⁶ = 64

Now ask this question:

2 raised to what power gives 32?

Answer:

5

Therefore,

log₂32 = 5

A logarithm simply tells us

How many times must we repeatedly multiply by the same number to reach a target value?

---

Another Example

Suppose

3¹ = 3

3² = 9

3³ = 27

3⁴ = 81

Now ask:

3 raised to what power gives 81?

Answer

4

Therefore,

log₃81 = 4

---

💡 Easy Definition

A logarithm answers this question:

“How many times do I repeatedly multiply (or divide) by the same number to reach my destination?”

---

✅ Example 7 – Multiplying by 2

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

This is completely different from

i = i + 2

---

Dry Run

Suppose

n = 32

Values become

1

2

4

8

16

32

Notice something?

Each iteration doubles the value.

---

Mathematical Analysis

Suppose after k iterations

2ᵏ = n

Taking logarithm,

k = log₂n

Therefore,

✅ Time Complexity = O(log n)

---

🚀 Why Is This So Fast?

Suppose

n = 1,000,000

A normal loop executes

1,000,000

iterations.

A logarithmic loop executes only about

20

iterations.

That is why algorithms like Binary Search are incredibly fast.

---

✅ Example 8 – Dividing by 2

for(int i = n; i > 0; i = i / 2)
{
    System.out.println(i);
}

---

Dry Run

Suppose

n = 64

Values become

64

32

16

8

4

2

1

---

Mathematical Analysis

Suppose after k iterations

n / 2ᵏ = 1

Rearranging,

2ᵏ = n

Taking logarithm,

k = log₂n

Therefore,

✅ Time Complexity = O(log n)

---

📌 Important Rule

Whenever the loop variable changes like

i *= 2

or

i *= 3

or

i /= 2

or

i /= 5

the complexity becomes

O(log n)

because the variable changes multiplicatively, not by a fixed amount.

---

✅ Example 9 – Square Root Complexity (O(√n))

One of the most common algorithms with O(√n) complexity is checking whether a number is prime.

Consider the following code.

int n = 100;

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

---

Step 1 – Initialization

int i = 1;

Runs only once.

---

Step 2 – Condition

i * i <= n

This means

i² ≤ n

Taking square root on both sides,

i ≤ √n

The loop continues only until the square root of n.

---

Dry Run

Suppose

n = 100

Values become

1

2

3

4

5

6

7

8

9

10

When

11 × 11 = 121

the condition becomes false.

The loop executes only

10

times.

Notice

√100 = 10

---

Another Example

Suppose

n = 64

The loop executes

1

2

3

4

5

6

7

8

because

8 × 8 = 64

Again,

√64 = 8

---

Time Complexity

The loop executes approximately

√n

times.

Therefore,

✅ Time Complexity = O(√n)

---

🌟 Why Do Programmers Write i * i <= n?

You may also see

for(int i = 1; i <= Math.sqrt(n); i++)

This is also O(√n).

However, experienced programmers prefer

for(int i = 1; i * i <= n; i++)

because

✅ It avoids repeatedly calling Math.sqrt().

✅ It uses integer arithmetic.

✅ It is the standard interview solution.

---

🌟 Real-World Example – Prime Number Check

One of the most famous O(√n) algorithms is checking whether a number is prime.

public class PrimeCheck {

    public static void main(String[] args) {

        int n = 97;
        boolean isPrime = true;

        if(n <= 1)
            isPrime = false;

        else {

            for(int i = 2; i * i <= n; i++) {

                if(n % i == 0) {
                    isPrime = false;
                    break;
                }
            }

        }

        if(isPrime)
            System.out.println("Prime Number");
        else
            System.out.println("Not Prime");
    }
}

---

🤔 Why Only Check Up to √n?

Suppose

n = 36

Its factors are

1 × 36

2 × 18

3 × 12

4 × 9

6 × 6

After reaching 6, the factors begin repeating in reverse.

9 × 4

12 × 3

18 × 2

36 × 1

Therefore,

once we’ve checked up to

√36 = 6

there is no need to continue.

This is why Prime Number checking can be done in O(√n) instead of O(n).

---

🧠 Memory Tricks

Whenever you see

i++

i += 2

i -= 3

➡️ Think

O(n)

---

Whenever you see

i *= 2

i /= 2

i *= 3

➡️ Think

O(log n)

---

Whenever you see

i * i <= n

or

Math.sqrt(n)

➡️ Think

O(√n)

---

📝 Part 2 Summary

In this part, we learned:

✅ Why decrementing by a constant is still O(n)

✅ Why i * 2 < n is O(n) and not O(log n)

✅ What a logarithm really means

✅ Why i *= 2 becomes O(log n)

✅ Why i /= 2 is also O(log n)

✅ What O(√n) means

✅ Why Prime Number checking uses O(√n)

---

📌 Coming Up in Part 3

In the final part of this guide, we’ll cover:

• ✅ Nested loops (O(n²))
• ✅ Triangular loops
• ✅ O(n log n)
• ✅ O(n³)
• ✅ Standard order of Big-O notations
• ✅ Common interview mistakes
• ✅ Quick revision table
• ✅ Final conclusion and practice tips

By the end of Part 3, you’ll have a complete understanding of the most common Time Complexity patterns asked in interviews and university exams.