Techniques for Determining Time Complexity of Iterative Algorithms

Core Technique: Counting Operations

To determine the time complexity of an iterative algorithm:
1. Identify the basic operations (comparisons, assignments, arithmetic)
2. Count how many times each operation is performed as a function of $n$
3. Express the total count in Big-O notation, keeping only the dominant term

KEY TAKEAWAY: Focus on the innermost operations of loops. The total count is the product of each loop’s iteration count.

Single Loop

for i ← 0 to n-1 do
    operation
end for

The operation executes $n$ times. Time complexity: $O(n)$

Nested Loops (both depend on n)

for i ← 0 to n-1 do
    for j ← 0 to n-1 do
        operation
    end for
end for

Outer loop: $n$ times. Inner loop: $n$ times per outer iteration. Total: $n \times n = n^2$ operations. Time complexity: $O(n^2)$

Nested Loops (inner depends on outer)

for i ← 0 to n-1 do
    for j ← 0 to i do
        operation
    end for
end for

Inner loop runs $1, 2, 3, \ldots, n$ times for each outer iteration.
\$$\text{Total} = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = O(n^2)$\$

Logarithmic Loop (input halved each iteration)

i ← n
while i > 1 do
    operation
    i ← i / 2
end while

$i$ takes values $n, n/2, n/4, \ldots, 1$. Number of iterations = $\log_2 n$. Time complexity: $O(\log n)$

Loop with Sequential Segments

for i ← 0 to n-1 do
    operation_A   // O(n)
end for
for j ← 0 to n-1 do
    operation_B   // O(n)
end for

Both loops run $O(n)$ sequentially. Total: $O(n) + O(n) = O(n)$.
(In Big-O, constant factors and lower-order terms are dropped.)

Loop with Logarithmic Inner Work

for i ← 0 to n-1 do    // n times
    heap_insert(pq, A[i])  // O(log n) each
end for

Total: $n \times O(\log n) = O(n \log n)$.

Worked Example: Bubble Sort

for i ← 0 to n-2 do
    for j ← 0 to n-i-2 do
        if A[j] > A[j+1] then
            swap(A[j], A[j+1])
        end if
    end for
end for

Inner loop runs $n-1, n-2, \ldots, 1$ times.
\$$\text{Total comparisons} = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2)$\$

Rules Summary

Loop Structure	Complexity
Single loop, $n$ iterations	$O(n)$
Two nested loops, each $n$	$O(n^2)$
Three nested loops, each $n$	$O(n^3)$
Loop halving input each step	$O(\log n)$
Single loop + $O(\log n)$ inner work	$O(n \log n)$
$k$ sequential loops of $O(n)$	$O(n)$

EXAM TIP: When analysing complexity, focus on the innermost operation and multiply by each enclosing loop count. Drop constants: $5n^2 \to O(n^2)$. Drop lower terms: $n^2 + n \to O(n^2)$.

Loop Structure	Complexity
Single loop, \(n\) iterations	\(O(n)\)
Two nested loops, each \(n\)	\(O(n^2)\)
Three nested loops, each \(n\)	\(O(n^3)\)
Loop halving input each step	\(O(\log n)\)
Single loop + \(O(\log n)\) inner work	\(O(n \log n)\)
\(k\) sequential loops of \(O(n)\)	\(O(n)\)

Time Complexity of Iterative Algorithms

Table of Contents

About these notes

Join StudyPulse