Analysis of Algorithms Best, Average, Worst Case: Tutorial, Examples, FAQs & Interview Tips

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.

Key Insight: A solution that feels fine for 100 elements may become completely impractical for 1,000,000 elements. Algorithm analysis helps catch that early.

What Do We Measure?

Algorithm analysis mainly focuses on two resources:

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?

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

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.

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)

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)

Priori and Posteriori Analysis

Algorithm analysis can be done in two broad ways.

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

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.

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)

2. Loop Analysis

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

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

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)

3. Recurrence Relations

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

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

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.

Key Takeaways

Algorithm analysis measures how efficient a solution is in terms of time and space.
Worst case gives the upper bound, best case gives the lower bound, and average case reflects typical behavior.
Priori analysis is theoretical and hardware-independent, while posteriori analysis is based on actual execution.
Common analysis methods include counting operations, analyzing loops, and solving recurrence relations.
Simplification rules such as dropping constants and lower-order terms help compare algorithms clearly.
A good algorithm is not only correct, but also scalable and resource-efficient.

Analysis of Algorithms Best, Average, Worst Case: Tutorial, Examples, FAQs & Interview Tips