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.

Types of Algorithm Analysis

Best, Average, and Worst Case

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

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.

How Algorithms Are Analyzed

There are several practical ways to analyze an algorithm.

1. Counting Basic Operations

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

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)

2. Loop Analysis

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

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)

3. Recurrence Relations

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

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.

Comparing Algorithms for the Same Problem

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

Common Mistakes in Algorithm Analysis

• 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.

Key Takeaways

• 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.