Ugenz Academy/Tutorial

Complexityanalysis

12 min read2,248 words

Reading progress

Keep learning

Complexity Analysis

Complexity Analysis is the process of measuring how efficiently an algorithm performs as the input size increases.

In simple words:

Complexity analysis tells us how much time and memory an algorithm needs.

There are two main types:

  1. Time Complexity → How much time an algorithm takes
  2. Space Complexity → How much extra memory an algorithm uses

1. Why Do We Need Complexity Analysis?

Suppose we have two algorithms that solve the same problem.

Algorithm A

Takes:

1 second

Algorithm B

Takes:

100 seconds

Both produce the correct answer, but Algorithm A is more efficient.

The problem becomes more interesting when the input gets bigger.

Suppose we have n items.

InputAlgorithm AAlgorithm B
101 sec2 sec
1,0001 sec20 sec
1,000,0001 sec20,000 sec

So we don't just want to know:

"How fast is it on my computer?"

We want to know:

"How does its performance grow when the input grows?"

That's what complexity analysis helps us understand.

2. What is Input Size?

We usually represent input size using n.

For example, suppose we have an array:

int arr[] = {10, 20, 30, 40, 50};

There are 5 elements.

So:

n = 5

If there are 1,000 elements:

n = 1000

If there are 1,000,000 elements:

n = 1,000,000

n simply represents the size of the input.

3. Time Complexity

Time complexity describes how the number of operations performed by an algorithm grows with input size.

For example:

int x = 10; int y = 20; int z = x + y;

These operations don't depend on n.

Whether your program has 10 items or 10 million items, these particular statements execute a fixed number of times.

So we consider this:

O(1)

4. Big O Notation

The most commonly used notation for complexity is Big O notation.

Examples:

O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)

Big O describes the growth rate of an algorithm.

You don't normally use Big O to say:

"This program takes exactly 2.35 seconds."

Instead, you say:

"This algorithm is O(n)."

5. O(1) — Constant Time

O(1) means the amount of work doesn't depend on the size of the input.

Example:

int arr[] = {10, 20, 30, 40, 50}; cout << arr[2];

We directly access index 2.

Whether the array contains:

5 elements

or:

5,000,000 elements

we can directly access arr[2].

Therefore:

Time Complexity = O(1)

Another example

int x = 10; x++;

Constant number of operations:

O(1)

6. O(n) — Linear Time

Now consider:

for(int i = 0; i < n; i++) { cout << arr[i]; }

If:

n = 5

the loop runs 5 times.

If:

n = 100

it runs 100 times.

If:

n = 1,000,000

it runs 1,000,000 times.

Therefore:

Time Complexity = O(n)

This is called linear time.

Example

Input size Operations 10 10 100 100 1,000 1,000 10,000 10,000

The operations grow directly with n.

7. O(n²) — Quadratic Time

Consider nested loops:

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

The outer loop runs:

n times

For every outer iteration, the inner loop also runs:

n times

Therefore:

n × n = n²

So:

Time Complexity = O(n²)

Example

If:

n = 10

operations ≈

10 × 10 = 100

If:

n = 100

operations ≈

100 × 100 = 10,000

If:

n = 1,000

operations ≈

1,000 × 1,000 = 1,000,000

This is why quadratic algorithms can become slow very quickly.

8. O(log n) — Logarithmic Time

O(log n) is very efficient.

A classic example is Binary Search.

Suppose you have:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

You want to find 13.

Instead of checking every number, binary search repeatedly cuts the search space roughly in half.

16 elements ↓ 8 elements ↓ 4 elements ↓ 2 elements ↓ 1 element

That's approximately:

log₂(n)

So:

Binary Search = O(log n)

This is much faster than O(n) for very large inputs.

9. O(n log n)

This complexity commonly appears in efficient sorting algorithms such as:

  • Merge Sort
  • Heap Sort
  • Average-case Quick Sort

For example:

n × log n

Therefore:

O(n log n)

It is generally more efficient than:

O(n²)

for large n.

10. O(2ⁿ) — Exponential Time

An algorithm with:

O(2ⁿ)

can become extremely expensive as n increases.

For example:

n = 1 → 2 n = 2 → 4 n = 3 → 8 n = 10 → 1,024 n = 20 → 1,048,576 n = 30 → 1,073,741,824

Exponential growth is very fast.

Some recursive solutions to problems can have exponential complexity if they repeatedly explore two or more possibilities.

11. O(n!)

O(n!) is even faster-growing.

Factorial means:

n! = n × (n-1) × (n-2) × ... × 1

For example:

5! = 120 10! = 3,628,800

Factorial complexity often appears in brute-force solutions involving permutations.

For example:

Try every possible ordering of n objects.

There are:

n!

possible arrangements.

12. Complexity Growth Comparison

From generally more efficient to less efficient:

O(1) ↓ O(log n) ↓ O(n) ↓ O(n log n) ↓ O(n²) ↓ O(2ⁿ) ↓ O(n!)

For large input sizes, the difference can be enormous.

13. How to Calculate Time Complexity

Let's learn the basic rules.

Rule 1: Ignore Constants

Consider:

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

Runs:

n times

Therefore:

O(n)

Now:

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

Total:

n + n = 2n

Big O ignores the constant 2.

Therefore:

O(2n) → O(n)

14. Rule 2: Drop Smaller Terms

Suppose:

O(n² + n)

For very large n, n² grows much faster than n.

Therefore:

O(n² + n) → O(n²)

Similarly:

O(n³ + n² + n) → O(n³)

And:

O(n + 100) → O(n)

15. Sequential Operations

Consider:

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

First loop:

O(n)

Second loop:

O(n)

Together:

O(n + n)

Therefore:

O(2n)

Drop the constant:

O(n)

16. Nested Loops

Consider:

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

Outer:

n

Inner:

n

Because the inner loop runs for every outer iteration:

n × n

Therefore:

O(n²)

Important rule

Sequential loops → Add Nested loops → Multiply

17. Different-Sized Nested Loops

Consider:

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

Outer loop:

n

Inner loop:

m

Therefore:

O(n × m)

or:

O(nm)

Don't automatically write O(n²) unless both loops depend on the same input size.

18. Logarithmic Example

Consider:

int i = 1; while(i < n) { i = i * 2; }

Values of i:

1 2 4 8 16 32 64 ...

The value doubles every iteration.

The number of iterations is approximately:

log₂(n)

Therefore:

O(log n)

19. Space Complexity

Time isn't the only thing we care about.

We also need to consider memory.

That's called space complexity.

Example:

int x;

Only a constant amount of additional memory is required.

Therefore:

Space Complexity = O(1)

20. O(n) Space

Consider:

int arr[n];

If n increases, the amount of memory required also increases.

Therefore:

Space Complexity = O(n)

Example:

n = 10 → memory for 10 elements n = 100 → memory for 100 elements n = 1000 → memory for 1000 elements

21. Time vs Space Complexity

These are different.

Consider:

int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; }

The loop runs n times:

Time = O(n)

But we only use a few extra variables:

sum i

So:

Extra Space = O(1)

Therefore:

Time Complexity → O(n) Space Complexity → O(1)

22. Best, Average and Worst Case

An algorithm can behave differently depending on the input.

Suppose we search for a number:

[10, 20, 30, 40, 50]

We want to find 10.

It's the first element.

Best Case

Found immediately:

O(1)

If we search for 50, we may need to check everything:

10 → 20 → 30 → 40 → 50

Worst Case

O(n)

The average case describes typical expected behavior over inputs, depending on the assumptions about those inputs.

23. Important: Big O Is Not Exact Running Time

Suppose two algorithms are:

Algorithm A → O(n) Algorithm B → O(n)

That doesn't necessarily mean they take exactly the same amount of time.

For example:

A → 2n operations B → 100n operations

Both are:

O(n)

Big O focuses on the growth rate, not exact execution time.

24. Why Constants Are Ignored

Suppose:

A = 10n B = 100n

For small inputs, the difference matters.

But complexity analysis focuses on what happens as n becomes very large.

Both grow linearly:

10n 100n

So both belong to:

O(n)

25. Common Complexity Examples

Code / AlgorithmTime Complexity
Access array elementO(1)
Single loopO(n)
Two separate loopsO(n)
Nested loopsO(n²)
Binary searchO(log n)
Efficient sortingO(n log n)
Some brute-force recursive algorithmsO(2ⁿ)
Generate all permutationsO(n!)

These are patterns you should learn to recognize.

26. A Very Important Example

Consider:

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

First part:

O(n)

Second part:

O(n²)

Total:

O(n + n²)

Drop the smaller term:

O(n²)

Therefore:

Time Complexity = O(n²)

27. Complexity Analysis Cheat Sheet

Remember these patterns:

Constant O(1) ↓ Doesn't depend on n Logarithmic O(log n) ↓ Input repeatedly divided Linear O(n) ↓ One pass through input Linearithmic O(n log n) ↓ Efficient sorting Quadratic O(n²) ↓ Two nested loops Exponential O(2ⁿ) ↓ Repeatedly exploring combinations Factorial O(n!) ↓ All permutations

28. The Main Rules to Remember

Rule 1

Single loop

for(...)

Usually:

O(n)

Rule 2

Nested loops

for(...) for(...)

Usually:

O(n²)

Rule 3

Separate loops

for(...) for(...)

Add them:

O(n + n) → O(n)

Rule 4

Nested different variables

O(n × m)

Rule 5

Repeatedly divide/multiply by a constant

O(log n)

Rule 6

Ignore constants

O(5n) → O(n)

Rule 7

Keep the fastest-growing term

O(n² + n) → O(n²)

29. Why Complexity Analysis Comes Before Arrays

Your DSA roadmap starts:

Introduction ↓ Complexity Analysis ↓ Arrays

This order is important.

When we study arrays, we'll not only learn:

"How does an array work?"

We'll also ask:

"How fast is accessing an element?"

"How fast is searching?"

"How fast is insertion?"

"How much memory does it use?"

For example, accessing:

arr[5]

is generally:

O(1)

But searching for an arbitrary value in an unsorted array can require:

O(n)

So complexity analysis gives us the language to evaluate the data structures and algorithms we study later.

Final Concept

The easiest way to remember this entire topic is:

Complexity Analysis │ ┌─────────┴─────────┐ ↓ ↓ Time Complexity Space Complexity │ │ How much work? How much memory? │ ┌─────┼─────┬─────┐ ↓ ↓ ↓ ↓ O(1) O(log n) O(n) O(n²)

And the central question is always:

"When my input becomes bigger, how does my algorithm's resource usage grow?"

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy