Introduction

When analyzing an algorithm, it is important to understand how its running time changes as the size of the input increases. Time complexity provides a way to describe this growth without measuring the exact time taken on a particular computer. Calculating time complexity involves examining the operations performed by an algorithm and determining how often those operations execute with respect to the input size.
For simple algorithms, this can often be done by counting loops and operations. For recursive algorithms, however, the analysis may require recurrence relations and techniques such as the Substitution Method, Recursion Tree Method, and Master Theorem.
This article explains a step-by-step approach for calculating time complexity from both iterative and recursive code.
 

Table of Contents

---

Steps to Calculate Time Complexity

A useful method for calculating time complexity is to follow these steps:

1. Identify the input size.
2. Identify the important or basic operation.
3. Determine how many times the operation executes.
4. Analyze loops and nested loops.
5. Analyze sequential operations separately.
6. Consider conditional statements and the case being analyzed.
7. Analyze recursive calls when recursion is used.
8. Express the total work as a function of n.
9. Remove constant factors and lower-order terms.
10. Keep the dominant term.

Identify the Input Size

The first step is to determine what represents the size of the input.

• Input Size: Usually, the input size is represented by n, but its meaning depends on the problem.
• Representation of n: For a list, n may represent the number of elements. For a string, n may represent the number of characters. For a matrix, the input may have multiple dimensions.
• Calculation: Therefore, before calculating complexity, determine what grows when the input becomes larger.

Identify the Basic Operation

The next step is to identify the operation whose execution count depends on the input size.

for number in numbers:
    print(number)

The operation inside the loop is performed once for each element.
If there are n elements, the operation is performed n times;

​​​​​Number of operations ≈ n

Therefore, the time complexity is O(n).

Analyzing a Single Loop

A loop that runs from 0 to n generally performs work proportional to n.

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

The loop executes n times.

n iterations = O(n)

Therefore, the time complexity is O(n).

Loops With Fixed Work

If a loop always runs a fixed number of times, its complexity is O(1).

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

This loop always executes 10 times regardless of the input size.

10 operations to O(1)

The important question is whether the number of iterations changes with n.

Analyzing Nested Loops

When one loop is placed inside another, and both depend on n, their iteration counts generally multiply.

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

The outer loop runs n times, and the inner loop runs n times for every iteration of the outer loop.

n × n = n²

Therefore, the time complexity is O(n²).

Loops With Different Ranges

Two nested loops do not automatically mean O(n²). Their ranges must be examined.

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

The outer loop runs n times, while the inner loop always runs 5 times.

n × 5 = 5n

After ignoring the constant factor:

O(5n) = O(n)

Therefore, the time complexity is O(n).

Analyzing Sequential Operations

When operations execute one after another, their complexities are generally added.

for number in numbers:
    print(number)
for number in numbers:
    print(number * 2)

Both loops run n times.

O(n) + O(n) = O(2n)

Ignoring the constant factor gives:

O(n)

Therefore, sequential operations are generally added, rather than multiplied.

Sequential Operations With Different Complexities

Consider an algorithm containing one linear operation followed by a quadratic operation:

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

The first part is O(n), while the second part is O(n²).

O(n) + O(n²) = O(n + n²)

The dominant term is n², so the final complexity is:

O(n²)

Analyzing Conditional Statements

A simple conditional statement usually performs a constant amount of work.

if number > 0:
    print("Positive")
else:
    print("Not positive")

The condition and each branch perform a fixed amount of work, so the complexity is O(1).
If a branch contains a loop, however, that loop must be analyzed separately.

Analyzing Logarithmic Loops

A loop can have logarithmic complexity when its variable is repeatedly multiplied or divided by a constant.

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

The value changes approximately as:

1 to  2 to 4 to  8 to 16  ...

The value doubles after every iteration, so the number of iterations grows logarithmically.
Therefore, the time complexity is O(log n).

Analyzing Dependent Nested Loops

Sometimes the inner loop does not execute n times for every iteration of the outer loop.

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

The total number of executions is approximately:

0 + 1 + 2 + 3 + ... + (n - 1)

This sum grows proportionally to n².
Therefore, the time complexity is O(n²).

Analyzing Recursive Algorithms

Recursive algorithms solve a problem by calling themselves on smaller inputs.
Consider a simple recursive function:

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)

Each call reduces n by 1 and makes one recursive call.
The recurrence relation can be written as:

T(n) = T(n - 1) + O(1)

Here, T(n-1) is the recursive call and O(1) is for the print statement. There are approximately n recursive calls, so the time complexity is O(n).

For recursive algorithms, it is often useful to write a recurrence relation that describes the work performed by the algorithm.

What Is a Recurrence Relation?

A recurrence relation expresses the running time of a recursive algorithm in terms of the running time of smaller inputs.
A common form for divide-and-conquer algorithms is:

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

Here:

• T(n) represents the running time for an input of size n.
• a represents the number of recursive subproblems.
• n/b represents the size of each smaller subproblem.
• f(n) represents the additional work performed outside the recursive calls.

This form is particularly important when analyzing divide-and-conquer algorithms.

Substitution Method

The Substitution Method solves a recurrence by first making a reasonable guess about the complexity and then proving that the guess is correct.

Consider:

T(n) = T(n - 1) + 1

Now for T(n-1)

T(n-1) = T(n-2)+1

Expanding the recurrence and replacing the T(n-1) from original:

T(n) = T(n - 2) + 1 + 1
or 
T(n) = T(n - 2) + 2

Continuing this process:

T(n) = T(n - k) + k

When k reaches n, the recurrence contains approximately n constant operations.

Therefore:

T(n) = O(n)

The Substitution Method is useful when the recurrence does not directly fit the Master Theorem.

Recursion Tree Method

The Recursion Tree Method represents recursive calls as a tree. Each level shows the work performed by a group of recursive calls.

Consider:

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

This recurrence represents an algorithm that divides the problem into two subproblems of size n/2 and performs n additional work.

At the first level, the work outside the recursive calls is:

n

At the next level, there are two subproblems, each doing n/2 work:

2 × n/2 = n

The next level also performs:

4 × n/4 = n

Therefore, each level contributes approximately n work.

The tree has approximately log n levels, giving:

n × log n

Therefore:

T(n) = O(n log n)

This technique is particularly useful for visualizing divide-and-conquer algorithms.

Master Theorem

The Master Theorem provides a direct way to solve many recurrence relations that have the form:

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

It is commonly used for divide-and-conquer algorithms, where a problem is divided into smaller subproblems of similar size.

To apply the Master Theorem, identify:

• a: the number of recursive subproblems.
• b: the factor by which the input size is reduced.
• f(n): the work performed outside the recursive calls.

The important comparison is between f(n) and n^log_ba.

Based on this comparison, the Master Theorem provides three main cases.

Case 1: If f(n) grows polynomially slower than n^log_ba, then:

T(n) = Θ(n^log_ba)

Case 2: If f(n) grows at the same rate as n^log_ba, then:

T(n) = Θ(n^log_ba log n)

Case 3: If f(n) grows polynomially faster than n^log_ba, under the regularity condition required by the theorem, then:

T(n) = Θ(f(n))

Master Theorem Example

Consider the recurrence for Merge Sort:

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

Identify the values:

• a = 2
• b = 2
• f(n) = O(n)

Now calculate:

n^log₂2 = n

Therefore, f(n) and n^log_ba grow at the same rate.
This corresponds to Case 2 of the Master Theorem.

Therefore:

T(n) = Θ(n^log₂2 log n)=Θ(n^log₂2 log n)

The algorithm creates two subproblems, each of size n/2, and performs O(n) additional work to combine their results. So the time complexity of Merge Sort is O(n log n).

When to Use Each Recurrence Method

Method	When It Is Useful
Substitution Method	When you can make and prove a suitable complexity bound for the recurrence.
Recursion Tree Method	When you want to visualize the work performed at each level of recursive calls.
Master Theorem	When the recurrence has the form T(n) = aT(n/b) + f(n) and satisfies the theorem's conditions.

Not every recurrence can be solved directly using the Master Theorem. In such cases, the Substitution Method, Recursion Tree Method, or another recurrence-solving technique may be more appropriate.

Ignore Constant Factors

When simplifying time complexity, constant factors are generally ignored.

O(5n) to O(n)

O(3n²) to O(n²)

The goal is to describe the overall growth rate rather than the exact number of operations.

Ignore Lower-Order Terms

When an expression contains multiple terms, the term that grows fastest usually determines the final asymptotic complexity.

For example:

O(n² + n + 10) = O(n²)

Here, n² is the dominant term because it grows faster than n and the constant 10.

Find the Dominant Term

Consider:

4n² + 3n + 20

Ignore the constant coefficients and lower-order terms:

O(4n² + 3n + 20) = O(n²)

The dominant term determines the simplified asymptotic growth.

Best Case, Average Case, and Worst Case

An algorithm may perform different amounts of work for different inputs of the same size.

Case	Description
Best Case	The minimum amount of work required for a particular input size.
Average Case	The expected amount of work under a specified model of possible inputs.
Worst Case	The maximum amount of work required for a particular input size.

For example, in linear search, if the target is the first element, the algorithm may finish immediately. If the target is the last element or is not present, the algorithm may inspect all n elements.

Complete Example: Analyzing an Algorithm

Consider the following algorithm:

def find_pairs(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            print(numbers[i], numbers[j])

Assume the list contains n elements.
The outer loop executes n times.
The inner loop does not execute n times for every iteration, but its total number of executions is approximately:

0 + 1 + 2 + ... + (n - 1)

This sum grows proportionally to n².
Therefore, the time complexity is:

O(n²)

This example demonstrates why simply counting loops is not enough. The number of times the operations actually execute must be considered.

Common Mistakes When Calculating Time Complexity

1.  Assuming every loop is O(n): Some loops run a fixed number of times, while others may be logarithmic.
2. Assuming every nested loop is O(n²): The ranges and dependencies of the loops must be examined.
3. Keeping constant factors: O(5n) simplifies to O(n).
4. Keeping lower-order terms: O(n² + n) simplifies to O(n²).
5. 5. Ignoring how variables change: A variable that doubles on every iteration behaves differently from one that increases by one.
6. Using the Master Theorem for every recursive algorithm: The recurrence must have the appropriate form and satisfy the theorem's conditions.
7. Confusing Big O with worst case: Big O describes an asymptotic upper bound. It is commonly used for worst-case analysis, but Big O itself does not automatically mean worst case.

Quick Reference

Pattern	Typical Complexity
Fixed number of operations	O(1)
One loop running n times	O(n)
Two nested loops, each running n times	O(n2)
Repeated doubling or halving	O(log n)
Sequential O(n) operations	O(n)
O(n) followed by O(n2)	O(n2)
T(n) = 2T(n/2) + O(n)	O(n log n)

Conclusion

Calculating time complexity is mainly about determining how the amount of work grows with the input size.
For iterative algorithms, examine loops, nested loops, sequential operations, conditions, and how loop variables change. For recursive algorithms, express the running time as a recurrence relation and solve it using an appropriate method.
The Substitution Method can be used to make and prove a suitable bound, the Recursion Tree Method helps visualize work across recursive levels, and the Master Theorem provides a direct solution for many divide-and-conquer recurrences.
After obtaining the operation count or recurrence solution, simplify the result by ignoring constant factors and lower-order terms and keeping the dominant growth term.
With practice, these patterns become easier to recognize, allowing you to calculate the time complexity of an algorithm systematically.

Frequently Asked Questions (FAQs)

1. How do I start calculating time complexity?

First, identify the input size n. Then determine which operations depend on n and how many times those operations execute.

2. How do I calculate the complexity of a single loop?

Determine how many times the loop executes as n grows. A loop that runs n times is generally O(n).

3. How do nested loops affect time complexity?

If two nested loops each execute approximately n times, their work generally multiplies to O(n²). However, their exact ranges must be examined.

4. Do sequential loops multiply their complexities?

No. Sequential operations are generally added. For example, O(n) followed by O(n²) gives O(n + n²), which simplifies to O(n²).

5. What is a recurrence relation?

A recurrence relation describes the running time of a recursive algorithm in terms of the running time of smaller inputs.