Time Complexity and Big‑O Notation (Beginner Friendly Guide)

1. Introduction

When we write a program, we often ask:

• Is my code fast enough?
• Will it work well when data becomes very large?

To answer these questions, we use Time Complexity.
Time Complexity helps us understand how the running time of a program grows as the input size increases.

2. What is Time Complexity?

Time Complexity tells us:

How much time an algorithm takes to run as input size increases

⚠️ Important:

It does NOT measure time in seconds.
It measures the number of operations.

Example idea:

• 5 numbers → program runs fast
• 1,000,000 numbers → program may become slow

Time complexity helps us predict this behavior.

3. What is Big‑O Notation?

Big‑O notation is a mathematical way to represent time complexity.
It describes the worst‑case performance of an algorithm.
We write time complexity like this:

• O(1)
• O(n)
• O(n²)
• O(log n)

Here:

• O means Order of
• n means input size

4. Why Do We Use Big‑O?

We use Big‑O because:

• Computers have different speeds
• Exact time depends on hardware
• Big‑O ignores machine differences

5. Important Big‑O Rules (Very Easy)

Rule 1: Ignore constants

for (int i = 0; i < n; i++) {
// code
}

➡ Runs n times → O(n)

for (int i = 0; i < 2 * n; i++) {
// code
}

➡ Still O(n)

We ignore 2, 3, 100, etc.

Rule 2: Single loop = O(n)

Any loop that runs from 0 to n is:
✅ O(n)

Rule 3: Nested loops = O(n²)

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// code
}
}

Outer loop → n
Inner loop → n
✅ Total = O(n × n) = O(n²)

Rule 4: Separate loops = Add

for (int i = 0; i < n; i++) { }
for (int j = 0; j < n; j++) { }

✅ O(n + n) → O(n)

6. Common Time Complexities (Very Important)

✅ O(1) – Constant Time

Always same time, no matter input size.

int x = arr[0];

Example:

• Accessing an array element

✅ O(n) – Linear Time

Time increases with input size.

for (int i = 0; i < n; i++) {
// code
}

Example:

• Searching an element in an unsorted array

✅ O(n²) – Quadratic Time

Slow for large data.

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// code
}
}

Example:

• Comparing every element with every other element

✅ O(log n) – Logarithmic Time

Very fast for big data.
Example:

• Binary Search

Each step reduces data into half.

✅ O(n log n)

Efficient sorting algorithms.
Examples:

• Merge Sort
• Quick Sort (average case)

Tell me your thoughts :)

Thanks,
Kailash
JavaCharter

Hope this was helpful!!