Mathematical Analysis of Algorithms

In the previous lesson, we learned how Big-O, Big-Theta, and Big-Omega describe algorithm performance.

Now we take the next important step: mathematically analyzing algorithms to determine their time complexity.

This lesson teaches you how to convert code into mathematical expressions and then simplify them to find complexity.

Why Mathematical Analysis Is Needed

When we write algorithms, we usually use loops, conditions, and nested logic.

To analyze performance, we must answer one question:

“How many times does each operation execute as input size grows?”

Mathematical analysis allows us to count operations in a structured way instead of guessing.

Step 1: Identify the Input Size

The first step is always to identify what represents the input size.

Examples:

• Array length → n
• Matrix size → n × n
• Number of nodes → n

Without defining n, complexity analysis is meaningless.

Simple Loop Analysis

Consider the following loop:

for i in range(n):
    print(i)

The loop runs exactly n times.

Each iteration performs a constant-time operation.

So the total time is:

T(n) = n

Which simplifies to:

O(n)

Multiple Sequential Loops

Now consider two loops running one after another:

for i in range(n):
    print(i)

for j in range(n):
    print(j)

The first loop runs n times. The second loop also runs n times.

So the total time is:

T(n) = n + n = 2n

In asymptotic analysis, constants are ignored.

So the complexity is still:

O(n)

Nested Loop Analysis

Nested loops increase complexity much faster.

for i in range(n):
    for j in range(n):
        print(i, j)

The outer loop runs n times.

For each outer iteration, the inner loop runs n times.

Total operations:

T(n) = n × n = n²

So the time complexity is:

O(n²)

Loops with Different Ranges

Not all nested loops run the same number of times.

for i in range(n):
    for j in range(i):
        print(i, j)

Here, the inner loop runs fewer times as i increases.

The total number of operations becomes:

1 + 2 + 3 + ... + (n − 1)

Which equals:

n(n − 1) / 2

Ignoring constants, we get:

O(n²)

Conditional Statements

Conditionals do not change complexity unless they contain loops.

if n > 0:
    print("Positive")
else:
    print("Zero or negative")

This runs in constant time:

O(1)

Worst-Case Analysis Is the Standard

When performing mathematical analysis, we usually focus on the worst-case scenario.

Why?

Because real systems must guarantee performance even under the heaviest load.

This is why Big-O is preferred in most real-world discussions.

Real-World Analogy

Imagine checking attendance in a classroom.

One loop: calling each student name once → O(n)

Nested loops: checking every student against every other student → O(n²)

As the class grows, the difference becomes huge.

Mini Practice

Think about the following:

• What happens if one loop runs n times and another runs n/2 times?
• Does dividing by 2 change Big-O?

Exercises

Quick Quiz

In the next lesson, we will apply this mathematical thinking to understand recursion and recursive algorithms.