Analysis of Algorithms Best, Average, Worst Case

Analysis of Algorithms

Analysis of algorithms is the process of studying how efficient an algorithm is before or after implementation. It helps us understand how much time and memory an algorithm needs as the input size grows.

Two algorithms may both solve the same problem correctly, but one may scale much better than the other. That is why analysis is a central part of Design and Analysis of Algorithms.

Why Do We Analyze Algorithms?

To compare solutions: We can choose the best approach among multiple correct algorithms.
To predict scalability: We can estimate how the algorithm behaves for large inputs.
To reduce waste: Good analysis helps avoid slow code and excessive memory usage.
To improve design: It reveals where optimization is needed.

What Do We Measure?

Algorithm analysis mainly focuses on two resources:

These measurements are usually expressed with asymptotic notation such as Big O, Omega, and Theta.

Measure	Meaning	Main Question
Time complexity	How running time grows with input size	How long will it take?
Space complexity	How memory usage grows with input size	How much memory will it use?

Types of Algorithm Analysis

Type	Meaning	Typical Notation	Why It Matters
Worst case	Maximum cost for input size n	O(f(n))	Gives a performance guarantee
Best case	Minimum cost for input size n	Omega(f(n))	Shows the most favorable situation
Average case	Expected cost over typical inputs	Theta(f(n)) or expected analysis	Represents more realistic behavior
Amortized analysis	Average cost per operation over a sequence	Amortized O(f(n))	Useful when occasional operations are expensive

Best, Average, and Worst Case

The same algorithm can behave differently depending on the input arrangement.

Algorithm	Best Case	Average Case	Worst Case
Linear Search	Omega(1)	Theta(n)	O(n)
Binary Search	Omega(1)	Theta(log n)	O(log n)
Insertion Sort	Omega(n)	Theta(n^2)	O(n^2)
Merge Sort	Theta(n log n)	Theta(n log n)	O(n log n)
Quick Sort	Omega(n log n)	Theta(n log n)	O(n^2)

Case Analysis Example

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Best case:
# target is at index 0
# comparisons = 1
# complexity = Omega(1)

# Worst case:
# target is at the last position or absent
# comparisons = n
# complexity = O(n)

# Average case:
# target is somewhere in the middle on average
# complexity = Theta(n)

Priori and Posteriori Analysis

Algorithm analysis can be done in two broad ways.

In DAA, priori analysis is the main focus because it lets us compare algorithms fairly. Posteriori analysis is still useful in real projects to validate actual performance.

Priori Analysis	Posteriori Analysis
Done before implementation	Done after implementation
Theoretical and mathematical	Experimental and measurement-based
Independent of hardware and language	Depends on machine, compiler, and environment
Uses asymptotic notation and proofs	Uses benchmarks, timing, and profiling

How Algorithms Are Analyzed

There are several practical ways to analyze an algorithm.

We count important operations such as assignments, comparisons, additions, or loop iterations.

For iterative code, we analyze how many times loops run and whether they are nested or sequential.

Recursive algorithms are often analyzed using a recurrence relation that describes how a problem of size n depends on smaller subproblems.

Pattern	Complexity	Reason
Single loop over n items	O(n)	One pass through data
Two nested loops over n items	O(n^2)	n multiplied by n
Loop that halves the input	O(log n)	Input shrinks rapidly
Outer loop n, inner loop log n	O(n log n)	Multiply both parts

Operation Counting

def sum_array(arr):
    total = 0
    for i in range(len(arr)):
        total += arr[i]
    return total

# total = 0 -> constant work
# loop runs n times
# body work per iteration is constant
# total complexity = O(n)

Loop Analysis Examples

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

# O(n)


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

# O(n^2)


def pattern3(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

# O(log n)

Recurrence Examples

def binary_search(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    return binary_search(arr, target, left, mid - 1)

# T(n) = T(n / 2) + O(1)
# Result: O(log n)


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# T(n) = 2T(n / 2) + O(n)
# Result: O(n log n)

Simplification Rules

After counting operations, we simplify the expression using standard asymptotic rules.

Rule	Example	Result
Drop constant factors	O(5n)	O(n)
Drop lower-order terms	O(n^2 + n)	O(n^2)
Sequential blocks add	O(n) + O(n^2)	O(n^2)
Nested blocks multiply	O(n) inside O(log n)	O(n log n)

Comparing Algorithms for the Same Problem

The real value of analysis appears when we compare multiple approaches to the same task.

Problem	Algorithm	Time	Space	Observation
Searching	Linear Search	O(n)	O(1)	Works on unsorted data
Searching	Binary Search	O(log n)	O(1)	Needs sorted data
Sorting	Bubble Sort	O(n^2)	O(1)	Simple but slow for large input
Sorting	Merge Sort	O(n log n)	O(n)	Faster but uses extra space
Fibonacci	Naive Recursion	O(2^n)	O(n)	Too slow for large n
Fibonacci	Dynamic Programming	O(n)	O(n) or O(1)	Much more practical

Analysis Of Algorithms Failure Cases

Keeping constants in the final answer, such as O(3n) instead of O(n).
Ignoring dominant terms, such as writing O(n^2 + n) instead of O(n^2).
Confusing best case, worst case, and average case.
Forgetting the cost of recursion or library methods.
Analyzing only time and ignoring space usage.

Analysis Of Algorithms Rules

Algorithm analysis helps compare solutions before full implementation.
Time and space complexity are the two main resources studied.
Worst case, best case, average case, and amortized analysis each answer different questions.
Loops, operation counting, and recurrence relations are common analysis tools.
Simplifying to the dominant growth term makes algorithm comparison easier.
A theoretically efficient algorithm usually scales better in practice too.

Before you move on