Skip to content
Software Engineering Hub

Time Complexity

Time complexity measures how the runtime of an algorithm scales with input size. It’s expressed using Big O notation.

How to Calculate Time Complexity

Step 1: Identify the Input Size

Usually n represents the main input (array length, string length, etc.).

Step 2: Count Operations

Count how many times basic operations execute relative to n.

Step 3: Keep the Dominant Term

Drop constants and lower-order terms.

Common Time Complexities

O(1) - Constant Time

Operations that don’t depend on input size.

def get_first(arr):
    return arr[0]  # Always 1 operation


def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]  # Always 3 operations → O(1)

O(log n) - Logarithmic Time

Halving the problem space each step.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:          # Runs log₂(n) times
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Why log n? If n = 16, we need 4 steps (16 → 8 → 4 → 2 → 1). log₂(16) = 4.

O(n) - Linear Time

Iterating through input once.

def find_sum(arr):
    total = 0
    for num in arr:     # Runs n times
        total += num    # O(1) per iteration
    return total
# Total: n × O(1) = O(n)

O(n log n) - Linearithmic Time

Common in efficient sorting algorithms.

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


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


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

O(n²) - Quadratic Time

Nested loops over the input.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):          # Runs n times
        for j in range(n - 1):  # Runs n-1 times
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Total: n × (n-1) = n² - n → O(n²)

O(2ⁿ) - Exponential Time

Doubling with each additional input element.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


# Each call makes 2 more calls
# Total calls roughly doubles each level → O(2ⁿ)

Analyzing Loops

Single Loop

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

Nested Loops (Independent)

for i in range(n):        # O(n)
    for j in range(n):    # O(n)
        print(i, j)
# Total: O(n) × O(n) = O(n²)

Nested Loops (Dependent)

for i in range(n):
    for j in range(i):    # Runs 0+1+2+...+(n-1) = n(n-1)/2
        print(i, j)
# Total: O(n²)

Loop with Halving

i = n
while i > 0:
    print(i)
    i = i // 2    # n → n/2 → n/4 → ... → 1
# Total: O(log n)

Loop with Doubling

i = 1
while i < n:
    print(i)
    i = i * 2    # 1 → 2 → 4 → ... → n
# Total: O(log n)

Analyzing Recursion

Linear Recursion

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n calls total → O(n)

Binary Recursion

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # O(2ⁿ)

Divide and Conquer

Use the Master Theorem for T(n) = aT(n/b) + O(n^d):

  • If d < log_b(a): O(n^log_b(a))
  • If d = log_b(a): O(n^d log n)
  • If d > log_b(a): O(n^d)

Merge Sort: T(n) = 2T(n/2) + O(n)

  • a=2, b=2, d=1
  • log₂(2) = 1 = d
  • Therefore: O(n log n)

Multiple Inputs

When you have multiple inputs, use different variables:

def print_pairs(arr1, arr2):  # arr1 has n elements, arr2 has m
    for a in arr1:            # O(n)
        for b in arr2:        # O(m)
            print(a, b)
# Total: O(n × m), NOT O(n²)

Sequential vs Nested

Sequential Operations (Add)

def process(arr):
    for x in arr:      # O(n)
        print(x)
    for x in arr:      # O(n)
        print(x * 2)
# Total: O(n) + O(n) = O(2n) = O(n)

Nested Operations (Multiply)

def process(arr):
    for x in arr:           # O(n)
        for y in arr:       # O(n)
            print(x, y)
# Total: O(n) × O(n) = O(n²)

Best, Average, Worst Case

AlgorithmBestAverageWorst
Linear SearchO(1)O(n)O(n)
Binary SearchO(1)O(log n)O(log n)
Quick SortO(n log n)O(n log n)O(n²)
Insertion SortO(n)O(n²)O(n²)

Big O typically represents the worst case unless specified otherwise.

Practice: Analyze These

Code 1
def mystery(n):
    count = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                count += 1
    return count

Answer: O(n³) - Three nested loops, each running n times.

Code 2
def mystery(n):
    count = 0
    i = 1
    while i < n:
        j = 1
        while j < n:
            count += 1
            j *= 2
        i *= 2
    return count

Answer: O(log²n) - Both loops run log(n) times.

Code 3
def mystery(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            print(arr[i], arr[j])

Answer: O(n²) - Inner loop runs n-1, n-2, …, 1 times = n(n-1)/2.

Key Takeaways

  1. Count operations relative to input size
  2. Drop constants and lower-order terms
  3. Nested loops multiply, sequential loops add
  4. log n appears when halving/doubling
  5. Use Master Theorem for divide-and-conquer recursion

Next Steps

Space Complexity Learn to analyze memory usage of algorithms