Algorithm Analysis

When you write code to solve a problem, there are always many ways to do it. Some ways are fast. Some are slow. Some work fine for small inputs but completely break when the input gets big.

Algorithm analysis is how we figure out: “How does my code behave as the input grows?”

This guide covers everything from scratch - no prior knowledge needed.

Why Do We Even Analyze Algorithms?

Imagine you have two ways to find a name in a list of 1 million people.

• Way 1: Check every name one by one -> could take 1 million steps
• Way 2: Use a smarter method -> could take just 20 steps

Both give the correct answer. But one is 50,000 times faster.

That difference matters in real life - your app either loads instantly or freezes.

So analysis helps us answer:

• Will this code be fast enough?
• Will it still work when a million users use it?
• Will it crash or hang on large input?

Types of Analysis

When we say “how fast is this algorithm?”, we need to ask: fast in what situation?

Best Case

This is the minimum time the algorithm will ever take.

Example: Searching for a name and it happens to be the very first one you check.

This is rarely useful in practice - you cannot count on being lucky every time.

Worst Case (Most Important)

This is the maximum time the algorithm can take.

Example: Searching for a name and it is the very last one, or not there at all.

Tip

In interviews and exams, always talk about the worst case unless someone specifically asks for something else.

Average Case

This is the expected time across all possible inputs.

It is hard to calculate and rarely asked about. Worst case is almost always what matters.

Asymptotic Notation - Big O, Omega, Theta

These are just symbols we use to describe how fast the running time grows as input gets bigger.

We do not care about exact time (like 4.2 seconds). We care about the shape of growth.

Big-O Notation - The Upper Bound (Worst Case)

Big-O tells you: “In the worst case, this algorithm will take at most this long.”

Example 1 - One loop:

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

This runs n times. So it is O(n) - linear time.

Example 2 - Two nested loops:

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

The inner loop runs n times, and the outer loop runs it n times -> total n x n = n². So it is O(n²) - quadratic time.

Big-O ignores constants and small terms:

O(3n + 10)  ->  O(n)
O(n² + n)   ->  O(n²)
O(5)        ->  O(1)

Why? Because when n is huge (like 1 billion), constants and smaller terms do not matter.

Omega (Ω) Notation - The Lower Bound (Best Case)

Omega tells you the minimum time an algorithm needs.

Rarely asked on its own. Useful for theory.

Theta (Θ) Notation - The Tight Bound

Theta is used when best case and worst case are the same order.

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

This always runs exactly n times - no more, no less. So it is Θ(n).

Note

For interviews, Big-O is enough. Theta and Omega are mostly for academic completeness.

Common Time Complexities (From Fastest to Slowest)

Notation	Name	What it means
O(1)	Constant	Same time no matter how big input is
O(log n)	Logarithmic	Cuts the problem in half each step
O(n)	Linear	One step per input item
O(n log n)	Linearithmic	Slightly more than linear (e.g., merge sort)
O(n²)	Quadratic	Nested loops - gets slow fast
O(2ⁿ)	Exponential	Doubles with each extra input - very bad

Visual feel for n = 10:

O(1)       ->  1 step
O(log n)   ->  3 steps
O(n)       ->  10 steps
O(n log n) ->  30 steps
O(n²)      ->  100 steps
O(2ⁿ)      ->  1024 steps - avoid!

Apriori vs Aposteriori Analysis

These are just two different timings of when you analyze code.

Apriori - Analyze Before Running

You look at the code (loops, recursion, input size) and figure out complexity without running it.

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

You can say: two loops, each runs n -> O(n²) - without ever executing it.

This is the standard way in computer science.

Aposteriori - Analyze After Running

You run the code and measure actual time on a computer.

The problem: results change based on hardware, language, operating system, etc. Not reliable for comparison.

Tip

Always prefer Apriori analysis. It is universal and does not depend on your machine.

Recurrence Relations

Some algorithms are recursive - they call themselves on a smaller version of the problem. For these, we cannot just count loops. We need a different tool: recurrence relations.

What is a Recurrence Relation?

A recurrence relation is just an equation that describes the running time of a recursive function in terms of itself on a smaller input.

Example - a simple recursive function:

def f(n):
    if n == 1:
        return
    f(n // 2)

How do we write the time taken?

• It makes one recursive call on input of size n/2 -> T(n/2)
• It does a small constant amount of work outside -> + 1

So the recurrence is:

$$T(n) = T(n/2) + 1$$

This equation does not directly tell you the answer. It just describes the pattern. You have to solve it.

Why Do Recurrences Matter?

They help analyze:

• Binary Search
• Merge Sort
• Quick Sort
• Divide and Conquer algorithms
• Any recursive algorithm

Ways to Solve a Recurrence

There are three main methods:

1. Back-Substitution Method - expand step by step until a pattern appears
2. Recursive Tree Method - draw the recursion as a tree and sum up the work
3. Master Theorem - a shortcut formula for common patterns

Back-Substitution Method

This is the most fundamental method. You expand the recurrence manually, step by step, until you can see a pattern, then you solve it.

The idea: “Replace the recursive part with its own definition, again and again, until you reach the base case.”

You do not guess the answer. You derive it.

General Form

Most recurrences you will see look like:

$$T(n) = T(n/b) + f(n)$$

Where b > 1 (the input shrinks each time) and f(n) is extra work done outside the recursive call.

Step-by-Step Example

Let us solve $T(n) = T(n/2) + n$, with base case $T(1) = c$.

1. Write the recurrence clearly

   $$T(n) = T(n/2) + n$$

2. First substitution - replace T(n/2)

   Since $T(x) = T(x/2) + x$, substitute $x = n/2$:

   $$T(n/2) = T(n/4) + n/2$$

   Plug back in:

   $$T(n) = T(n/4) + n/2 + n$$

3. Second substitution - replace T(n/4)

   $$T(n/4) = T(n/8) + n/4$$

   Plug back in:

   $$T(n) = T(n/8) + n/4 + n/2 + n$$

4. Find the general pattern after k substitutions

   After k steps, the pattern becomes:

   $$T(n) = T(n / 2^k) + n \cdot (1 + 1/2 + 1/4 + ... + 1/2^(k-1))$$

5. Stop at the base case

   We stop when $n / 2^k = 1$.

   Solving: $2^k = n$, so $k = \log_2 n$.

6. Substitute k into the expression

   $$T(n) = T(1) + n \cdot (1 + 1/2 + 1/4 + \cdots)$$

   Since $T(1) = c$:

   $$T(n) = c + n \cdot (1 + 1/2 + 1/4 + \cdots)$$

7. Sum the series using the GP formula

   The formula for $1 + r + r^2 + ... + r^(m-1)$ is:

   $$(1 - r^m) / (1 - r)$$

   Here $r = 1/2$ and $m = \log_2 n$, so:

   $$Sum = (1 - (1/2)^(log_2 n)) / (1 - 1/2)$$

   Since $(1/2)^(log_2 n) = 1/n$:

   $$Sum = (1 - 1/n) / (1/2) = 2 - 2/n$$

8. Final simplification

   $$T(n) = c + n \cdot (2 - 2/n) = c + 2n - 2$$

   Drop constants:

   $$T(n) = \Theta(n)$$

Key Rules for Back-Substitution

1. Never jump to the answer - always expand step by step
2. Stop only when you hit the base case
3. Solve for k mathematically
4. Use sum formulas only at the end
5. Drop constants only in the very last step

AP and GP - The Math You Need

When you do back-substitution, you end up with a series of numbers you need to sum. That sum is either an Arithmetic Progression (AP) or a Geometric Progression (GP).

Quick Memory Rule

• Same difference between terms -> AP (Arithmetic)
• Same ratio between terms -> GP (Geometric)

Example - is this AP or GP?

2, 4, 8, 16, ...   each term x 2   -> GP (ratio = 2)
2, 5, 8, 11, ...   each term + 3   -> AP (difference = 3)

Arithmetic Progression (AP) Sum Formula

$$S_n = (n/2) * [ 2a + (n-1) * d ]$$

Symbol	Meaning
$S_n$	Sum of all terms
$a$	First term
$d$	Common difference (what you add each time)
$n$	Number of terms

Geometric Progression (GP) Sum Formula

When $r < 1$:

$$S_n = a * (1 - r^n) / (1 - r)$$

When $r > 1$:

$$S_n = a * (r^n - 1) / (r - 1)$$

Symbol	Meaning
$a$	First term
$r$	Common ratio (what you multiply each time)
$n$	Number of terms

Special GP - When First Term is 1

This one comes up a lot in algorithm analysis:

$$1 + r + r^2 + ... + r^m = (1 - r^(m+1)) / (1 - r), where r is not 1$$

Symbol	Meaning in algorithm context
$1$	Cost at the root level
$r$	Ratio of work between levels
$m$	Index of the last level
$r^m$	Cost at the last level
$m+1$	Total number of levels

Recursive Tree Method

This method is the same as back-substitution, but instead of doing algebra, you draw a tree and add up the cost at each level.

The Idea

Every recursive call is a node in the tree. Each level of the tree represents one round of expansion. You:

1. Draw the tree level by level
2. Figure out the cost at each level
3. Count the number of levels
4. Add everything up

Example - Same Recurrence

$$T(n) = T(n/2) + n$$

Level 0 (root): problem size n, cost = n

Level 1: problem size n/2, cost = n/2

Level 2: problem size n/4, cost = n/4

…

Level k: problem size n/2^k, cost = n/2^k

We stop when size = 1, so k = log₂ n levels.

Total cost - sum of all levels:

$$n + n/2 + n/4 + \cdots + 1$$

This is a GP with $a = n$, $r = 1/2$, and $\log_2 n$ terms:

$$= n * (1 - (1/2)^(log_2 n)) / (1 - 1/2) = n * (2 - 2/n) = 2n - 2$$ $$T(n) = \Theta(n)$$

Same answer as back-substitution - just a different way to think about it.

Tip

Use the recursive tree method when you want to visualize what is happening. Use back-substitution when you want to be more formal and show your work step by step. Both give the same answer.

Master Theorem - The Shortcut

The Master Theorem is a ready-made formula for solving recurrences of a specific common form. Instead of expanding step by step, you just plug in numbers and read off the answer.

When Can You Use It?

The recurrence must look exactly like this:

$$T(n) = a \cdot T(n/b) + \Theta(n^k \cdot \log^p n)$$

Where:

• a = number of subproblems (how many recursive calls)
• b = how much the input shrinks each call (b > 1)
• k = the power of n in the extra work outside the recursion
• p = the power of log n in the extra work (often 0)

Constraints: a >= 1, b > 1, k >= 0.

Examples that fit this form:

• $T(n) = 2T(n/2) + n^2$ - yes, fits
• $T(n) = T(n/4) + n \log n$ - yes, fits

The Three Cases

Compare $\log_b a$ and $k$:

Case 1 - If $\log_b a > k$ (recursion dominates):

$$T(n) = Theta( n^(log_b a) )$$

Case 2 - If $\log_b a = k$ (recursion and work are balanced):

• If $p > -1$: $T(n) =$ Theta( n^k * log^(p+1) n )
• If $p = -1$: $T(n) = \Theta(n^k \cdot \log \log n)$
• If $p < -1$: T(n) = Theta( n^k )

Case 3 - If $\log_b a < k$ (extra work dominates):

• If $p \geq 0$: T(n) = Theta( n^k * log^p n )
• If $p < 0$: T(n) = Theta( n^k )

Master Theorem Example

Solve: $T(n) = 2T(n/2) + n$

Step 1 - Identify values: $a = 2$, $b = 2$, $f(n) = n = n^1 \cdot \log^0 n$, so $k = 1$ and $p = 0$.

Step 2 - Compute $\log_b a$:

$$\log_2 2 = 1$$

Step 3 - Compare: $\log_b a = 1 = k = 1$, so we are in Case 2, and $p = 0 > -1$.

Step 4 - Apply formula:

$$T(n) = Theta( n^1 * log^(0+1) n ) = Theta( n log n )$$

Answer: $T(n) = \Theta(n \log n)$ - this is Merge Sort’s complexity!

Caution

The Master Theorem only works when the recurrence fits the exact form $T(n) = aT(n/b) + f(n)$. If the subproblems have different sizes, or the recursion does not divide cleanly, use back-substitution or the tree method instead.

Picking the Right Method

Situation	Best Method
You want to understand the derivation deeply	Back-Substitution
You want to visualize what is happening	Recursive Tree
The recurrence fits $a \cdot T(n/b) + f(n)$	Master Theorem
Recurrence does not fit Master Theorem	Back-Sub or Tree

Quick Reference Cheat Sheet

Big-O (Worst Case)

How slow can it get? O(n²) means at most n² steps. Drop constants and smaller terms.

Recurrence Relation

Describes recursive time: T(n) = T(n/2) + 1. Does not give the answer directly - you must solve it.

Back-Substitution

Expand step by step, find the pattern, stop at the base case, sum the series.

Recursive Tree

Draw the call tree level by level. Sum costs at each level. Total levels = log n usually.

GP vs AP

Same ratio between terms -> GP. Same difference between terms -> AP. Use the right formula to sum.

Master Theorem

Shortcut for T(n) = aT(n/b) + f(n). Compare log_b(a) with k to pick Case 1, 2, or 3.

Summary

Analysis Types

• Best case - fastest possible run, rarely useful
• Worst case - slowest possible run, always use this
• Average case - expected run, hard to compute
• Apriori - analyze before running (preferred)
• Aposteriori - measure after running (hardware-dependent)

Notations

• O(f(n)) - upper bound, worst case growth
• Omega(f(n)) - lower bound, best case growth
• Theta(f(n)) - tight bound, both cases same
• Drop constants: O(3n) = O(n)
• Drop smaller terms: O(n² + n) = O(n²)

Solving Recurrences

1. Write the recurrence clearly with base case
2. Choose a method: back-sub, tree, or Master Theorem
3. For back-sub: expand k times, find k from base case, sum the series
4. For Master Theorem: identify a, b, k, p then compare log_b(a) with k
5. Always drop constants in the final answer

Tip

The fastest way to get comfortable with this is to practice solving recurrences by hand. Pick any recursive algorithm (binary search, merge sort), write its recurrence, and solve it using all three methods. You will see they always give the same answer - just different paths to get there.