Self-checkedTier 1 12 min readalgo.algorithm-analysis

Analysing loops, time and space

How to find the running time and the space of an algorithm: the machine model, input size, best, worst and average case, rules for sequences, nested and dependent loops, logarithmic and harmonic loops, recursion depth as space, and why a loop up to the value of the input is exponential in the input size.

Why it exists

The notation tells us how to state the growth of a cost. This page is about finding it: reading a piece of code, deciding what to count, and turning loops into sums. Almost every GATE question on complexity is of this kind: "what is the time complexity of this function?"

Prerequisites

Asymptotic notation

You need asymptotic notation and the standard sums (asymptotic notation).

Precise definitions

Model of computation (the RAM model). A single processor executes instructions one after another; each basic operation (an arithmetic operation, a comparison, an assignment, a memory access, a jump) takes one unit of time, and memory is unlimited and directly addressable. The running time of an algorithm on an input is the number of basic operations; counting only the dominant operation (for example comparisons in sorting) gives the same order if every other operation is done a bounded number of times per counted one.

Input size. The measure $n$ that the cost is expressed in: the number of elements for an array, the number of vertices and edges for a graph, and for a number the number of bits needed to write it, not its value.

Best, worst and average case. For a given $n$ there are many inputs.

Worst case $T_{\text{worst}}(n)$ : the maximum number of operations over all inputs of size $n$ (the usual measure, an upper bound for all inputs).
Best case $T_{\text{best}}(n)$ : the minimum.
Average case $T_{\text{avg}}(n)$ : the expected number of operations over a stated probability distribution of the inputs (often all inputs equally likely); it needs an assumption and a calculation.

"The time complexity is $O(f(n))$ " without further words is read as an upper bound on the worst case. $O$ , $\Omega$ , $\Theta$ are not the same thing as worst, best, average: each case has its own function, and each function can be described by any of the three notations.

Space. The memory used beyond the input: the auxiliary space. For a recursive algorithm it includes the recursion stack: if the recursion depth is $d$ and each call uses constant space, the space is $\Theta(d)$ . Space is often the number of simultaneously live objects, not the total ever allocated.

Counting rules for loops.

Sequence: add the costs; the order is that of the larger one. $\Theta(n) + \Theta(n^2) = \Theta(n^2)$ .
Conditional (if/else): worst case is the maximum of the branches plus the test.
Loop: the total cost is the sum over the iterations of the cost of the body. If the body costs the same each time, multiply by the number of iterations.
Nested loops with independent bounds multiply: $n \cdot m$ .
Dependent bounds: write the double sum. $\sum_{i=0}^{n-1} i = n(n-1)/2 = \Theta(n^2)$ .
Multiplying counters (i *= 2, i = i * 3): the number of iterations is a logarithm: $\lceil \log_2 n \rceil$ for for (i = 1; i < n; i *= 2). Dividing counters behave the same.
Adding to a counter that grows with the outer loop (for (j = 1; j <= n; j += i) inside i = 1 ... n): the inner loop runs $\lceil n/i \rceil$ times, and $\sum n/i = n H_n = \Theta(n \log n)$ (the harmonic sum).
Geometric sums: if the inner count doubles with the outer index (i *= 2, inner loop up to i), the total is a geometric series dominated by its last term: $1 + 2 + 4 + \cdots + n = \Theta(n)$ , not $\Theta(n \log n)$ .
Recursion: write a recurrence for the cost and solve it (next pages).
Loops up to the value: for (i = 2; i * i <= n; i++) takes $\Theta(\sqrt n)$ steps, which is $\Theta(2^{b/2})$ when $n$ has $b$ bits: exponential in the input size. Such time is called pseudo-polynomial when the number appears in the input as a value (for example in the 0/1 knapsack algorithm).

How it works

The C program below counts the innermost statement of five loop nests for $n$ = 4, 8, 16, 32, 64. It was compiled and run, and the table that follows is built from this very output together with the closed forms.

#include <stdio.h>
 
static long k1(int n) { long c = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) c++; return c; }
static long k2(int n) { long c = 0; for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) c++; return c; }
static long k3(int n) { long c = 0; for (int i = 1; i < n; i *= 2) c++; return c; }
static long k4(int n) { long c = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j += i) c++; return c; }
static long k5(int n) { long c = 0; for (int i = n / 2; i <= n; i++) for (int j = 1; j <= n; j *= 2) c++; return c; }
 
int main(void) {
    int ns[] = {4, 8, 16, 32, 64};
    printf("%-3s %6s %6s %6s %6s %6s\n", "n", "K1", "K2", "K3", "K4", "K5");
    for (int t = 0; t < 5; t++) {
        int n = ns[t];
        printf("%-3d %6ld %6ld %6ld %6ld %6ld\n", n, k1(n), k2(n), k3(n), k4(n), k5(n));
    }
    return 0;
}

n       K1     K2     K3     K4     K5
4       16      6      2      9      9
8       64     28      3     24     20
16     256    120      4     61     45
32    1024    496      5    145    102
64    4096   2016      6    337    231

The measured counts equal the closed forms. $K_1$ quadruples when $n$ doubles ( $n^2$ ); $K_2$ is $n(n-1)/2$ ( $0 + 1 + \cdots + (n-1)$ ); $K_3$ gains one per doubling ( $\log_2 n$ ); $K_4$ grows a little faster than $n$ (the harmonic sum, $n \ln n$ in order); $K_5$ is about $\tfrac n2 \log_2 n$ .

Counting the operations of five loop nests: start

Computed by a script, not typed

	code	n = 4	n = 8	n = 16	n = 32	n = 64	closed form	order
K1
K2
K3
K4
K5

Step 0

Five loop nests. The counts in the n columns were measured by compiling and running the C program of the page (the counter c is incremented in the innermost statement). The closed form is derived by hand and compared with every measured value.

0 / 5

computed by script: the quantities are evaluated or measured, one row at a time. python3 scripts/gen-algo-traces.py

Worked examples

EX 1Dependent inner loop

Easy

for (i = 0; i < n; i++) for (j = 0; j < i; j++) c++; is $K_2$ . For fixed $i$ the inner loop runs $i$ times, so the total is $\sum_{i=0}^{n-1} i = n(n-1)/2$ . For $n = 64$ this is $2016$ , as measured. The order is $\Theta(n^2)$ although the number of operations is half of $K_1$ : constants do not matter.

EX 2A logarithmic loop

Easy

for (i = 1; i < n; i *= 2) c++; runs while $2^k < n$ : for $n = 64$ , $i$ takes the values 1, 2, 4, 8, 16, 32: six iterations, $\lceil \log_2 64 \rceil = 6$ . For i = i * 3 the base is 3 but the order is the same: $\Theta(\log n)$ , since $\log_3 n = \Theta(\log_2 n)$ . The loop for (i = 2; i < n; i = i * i) squares the counter: 2, 4, 16, 256, ...: only about $\log_2 \log_2 n$ iterations (checked for $n = 2^{2^k}$ ).

EX 3Geometric inner bound: Theta(n), not Theta(n log n)

Medium

for (i = 1; i <= n; i *= 2) for (j = 1; j <= i; j++) c++;. The outer loop runs $\log_2 n + 1$ times and the inner loop runs $i = 1, 2, 4, \ldots, 2^{\lfloor \log_2 n \rfloor}$ times. For $n = 2^m$ the total is $1 + 2 + \cdots + 2^m = 2n - 1$ , a geometric series dominated by its last term: $\Theta(n)$ . A common mistake is to multiply " $\log n$ iterations" by "up to $n$ per iteration" and answer $n \log n$ . In the same way for (i = n; i > 1; i /= 2) for (j = 0; j < i; j++) takes $n + n/2 + n/4 + \cdots = 2n - 2$ steps: $\Theta(n)$ . (Both closed forms were checked for $n = 2, 4, \ldots, 4096$ .)

EX 4The harmonic sum and the square-root loop

Medium

for (i = 1; i <= n; i++) for (j = i; j <= n; j += i) c++; runs the inner loop $\lfloor n/i \rfloor$ times, so the total is $\sum_{i=1}^{n} \lfloor n/i \rfloor = \Theta(n \log n)$ : for $n = 10^4$ the count divided by $n \ln n$ is about 1. In contrast for (i = 1; i * i <= n; i++) c++; stops at $\lfloor \sqrt n \rfloor$ : $\Theta(\sqrt n)$ iterations. The triple loop for i < n; for j < i; for k < j counts $\binom{n}{3} = n(n-1)(n-2)/6 = \Theta(n^3)$ , since choosing $k < j < i$ is choosing three of the $n$ values.

EX 5Best, worst and average case; time versus input size

GATE level

Linear search for a key in an array of $n$ elements: best case 1 comparison (key first), worst case $n$ (key last or absent), average case for a successful search with the key equally likely at any of the $n$ positions: $(1 + 2 + \cdots + n)/n = (n+1)/2$ ; all three are described exactly by $\Theta$ ( $\Theta(1)$ , $\Theta(n)$ , $\Theta(n)$ ). The statement "linear search is $O(n)$ " is true for all cases, " $\Omega(n)$ " is true only for the worst case. And consider testing whether $n$ is prime by trying every divisor up to $\sqrt n$ : it takes $\Theta(\sqrt n)$ steps, which looks fast, but if the input is the number written in $b$ bits ( $n \approx 2^b$ ) it is $\Theta(2^{b/2})$ : exponential in the input size. Questions about "polynomial time" refer to the number of bits.

Cheat box

RAM model: each basic operation costs one unit. Input size: number of elements, or number of bits of a number.
Worst, best, average case are different functions; $O$ , $\Omega$ , $\Theta$ are bounds on any of them.
Sequence: add (take the larger). Nested independent loops: multiply. Dependent bounds: write the sum.
i *= 2 loops run $\log n$ times; i = i * i loops run $\log \log n$ times.
Inner loop up to a doubling counter: geometric, $\Theta(n)$ in total. Inner loop j += i: harmonic, $\Theta(n \log n)$ .
i * i <= n: $\Theta(\sqrt n)$ . A loop up to the value $n$ is exponential in the bit length.
Space = auxiliary memory, including the recursion stack (depth times frame size).
$\sum_{i < n} i = n(n-1)/2$ , $\sum \lfloor n/i \rfloor = \Theta(n \log n)$ .

Traps and GATE patterns

Connections

Builds on

Asymptotic notation

Unlocks

Amortized analysisPrerequisite ofplanned

P, NP and NP-completeness (outside syllabus, appeared in earlier papers)Prerequisite ofplanned

Asymptotic notationimplemented by Solving recurrences: substitution, tree and Master theoremuses Linear and binary searchPrerequisite of Linear and binary searchuses Bubble, selection and insertion sortPrerequisite of Bubble, selection and insertion sortuses Greedy method and exchange argumentPrerequisite of Greedy method and exchange argumentuses Control flow and loopsuses

Across subjects

Recursion and the call stackuses

Within this subject

Asymptotic notationuses Solving recurrences: substitution, tree and Master theoremimplemented-by Linear and binary searchimplemented-by

The notation is explained in asymptotic notation. Recursive algorithms lead to recurrences, solved in solving recurrences; the best, worst and average cases of the first concrete algorithm are in linear and binary search. The stack frames that make recursion cost space are the ones of recursion and the call stack.

PYQs

22 previous year questions from your book. I re-solved each one myself (19 by running or simulating, 3 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2023 · MSQ · 2 marksQ8 · page 98 of the book

Consider functions Function 1 and Function 2
expressed in pseudocode as follows:Function 1
and Function 2

Function 1
while n > 1 do
for i = 1 to n
do
x = x + 1;
end for
n = ⌊n/2⌋;
end while
Function 2
for i = 1 to 100 * n
do
x = x + 1;
end for
Let f1(n) and f2(n) denote the number of times the
statement x = x + 1; is executed in Function 1 and
Function 2, respectively.

(a)f1 (n) ∈⁡θ(f2 (n))
(b)f1 (n) ∈⁡o(f2 (n))
(c)f2 (n) ∈ ω(f1 (n))
(d)f1 (n) ∈ O(n)

GATE 2017 · Set 2 · MCQ · 2 marksQ15 · page 99 of the book

Consider the following C function
int fun(int n) {
int i, j;
for(i=1; i<=n; i++) {
for (j=1; j<n; j+=i) {
printf("%d %d", i, j);
}
}
}
Time complexity of fun in terms of θ notation is

(a)θ ( n✓n )
(b)θ(n2)
(c)θ(n log n)
(d)θ(n2 log n)

GATE 2016 · Set 2 · NATQ17 · page 99 of the book

The given diagram shows the flowchart for a
recursive function A(n). Assume that all
statements, except for the recursive calls, have
O(1) time complexity. If the worst-case time
complexity of this function is O(nα ), then the least
possible value (accurate up to two decimal
positions) of α is
.
Flowchart for Recursive Function A(n)

GATE 2015 · Set 1 · MCQ · 2 marksQ18 · page 99 of the book

Consider the following C function.
int fun1 (int n)
{
int i, j, k, p, q = 0;
for (i = 1; i< n; ++i)
{
p = 0;
for (j = n; j > 1; j = j/2)
++p;
for (k = 1; k < p; k = k*2)
++q;
}
return q;
}
Which one of the following most closely
approximates the return value of the function fun1?

(a)n3
(b)n(logn)2
(c)nlogn
(d)nlog(logn)

GATE 2014 · Set 3 · NAT · 2 marksQ22 · page 100 of the book

Suppose we have a balanced binary search tree T
holding n numbers. We are given two numbers L
and H and wish to sum up all the numbers in T that
lie between L and H. Suppose there are m such
numbers in T. If the tightest upper bound on the
time to compute the sum is
O(na logb n + mc logd n)
the value of a + 10b + 100c + 1000d is
.
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is

(a)Θ(n2)
(b)Θ(n2log n)
(c)Θ(n3)
(d)Θ(n3log n)

GATE 2013 · Set 3 · MCQQ24 · page 100 of the book

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
The equality above remains correct if X is
replaced by

(a)Only I
(b)Only II
(c)I or III or IV but not II
(d)II or III or IV but not I

GATE 2012 · MCQ · 1 markQ25 · page 100 of the book

Let W(n) and A(n) denote respectively, the worst
case and average case running time of an algorithm
executed on an input of size n. Which of the
following is ALWAYS TRUE?

(a)A(n) = Ω (W(n))
(b)A(n) = Θ (W(n))
(c)A(n) = O (W(n))
(d)A(n) = o (W(n)) ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank ! 2

GATE 2008 · MCQ · 2 marksQ31 · page 101 of the book

Consider the following C functions:int f1(int n)
{
Which one of the following represents the time
complexity of the algorithm?

(a)θ (n)
(b)θ (n log n)
(c)θ (n2)
(d)θ (n2logn)

GATE 2007 · MCQ · 1 markQ32 · page 102 of the book

Exponentiation is a heavily used operation in
public key cryptography. Which of the following
options is the tightest upper bound on the number
of multiplications required to compute bnmod
m,0≤b , n≤m?

(a)O(logn)
(b)O(√n )
(c)O(n/logn)
(d)O(n)

GATE 2007 · MCQQ33 · page 102 of the book

In the following C function, let n≥m.
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
How many recursive calls are made by this
function?

(a)θ(logn)
(b)ω(n)
(c)θ(loglogn)
(d)Θ(√ n )

GATE 2007 · MCQ · 1 markQ34 · page 102 of the book

Consider the following C code segment: int
IsPrime(n)
{

GATE 2006 · MCQ · 1 markQ36 · page 102 of the book

Consider the following C-program fragment in
which i, j, and n are integer variables.
for (i = n, j = 0; i > 0; i/=2, j += i);
Let Val(j) denote the value stored in the variable j
after termination of the for loop. Which one of the
following is true?

(a)val(j)= θ (logn)
(b)val(j)= θ (sqrt(n))
(c)val(j)= θ (n)
(d)val(j)= θ (nlogn)

GATE 2006 · MCQ · 1 markQ37 · page 102 of the book

Consider the following recurrence:

T(n) = 2T([√n]) + 1, T(1) = 1
Which one of the following is true?
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Primen"); return 0;}
return 1;
} Let T(n)denote the number of times the for
loop is executed by the program on input n.
Which of the following is TRUE?

(a)T(n)=O(√n ) and T(n)=Ω(√n )
(b)T(n)=O(n) and T(n)=Ω(√n )
(c)T(n)=O(√n ) and T(n)=Ω(1)
(d)None of the above
(a)T(n)= θ (loglogn)
(b)T(n)= θ (logn)
(c)T(n)= θ (√n)
(d)T(n)= θ (n)

GATE 2005 · MCQ · 1 markQ40 · page 103 of the book

Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}
Suppose we modify the above function foo() and
store the values of foo (i), 0⁡≤⁡i < n, as and
when they are computed. With this modification,
the time complexity for function foo() is
significantly reduced. The space complexity of
the modified function would be:

(a)O(1)
(b)O(n)
(c)O(n!)
(d)O(nn)

GATE 2026 · Set 2 · MCQ · 2 marksQ1 · page 144 of the book

Consider an array A of integers of size n. The
indices of A run from 1 to n. An algorithm is to
be designed to check whether A satisfies the
condition given below.
for all i, j {1, ..., n - 1} such that i > j,
( A[i + 1] - A[i] ) > ( A[j + 1] - A[j] )
Which one of the following gives the worst case
time complexity of the fastest algorithm that can
be designed for the problem?

(a)Θ(n)
(b)Θ(logn)
(c)Θ(nlogn)
(d)Θ(n2)

GATE 2024 · Set 1 · MCQ · 1 markQ3 · page 144 of the book

Given an integer array of size N, we want to check
if the array is sorted (in either ascending or
descending order). An algorithm solves this
problem by making a single pass through the array
and comparing each element of the array only with
its adjacent elements. The worst-case time
complexity of this algorithm is

(a)Both O(n)and Ω (n)
(b)O(n) but not Ω (n)
(c)Ω (n) but not O(n)
(d)Neither O(n) nor Ω (n) v Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2015 · Set 1 · MCQ · 2 marksQ8 · page 147 of the book

An algorithm performs (logN)1/2 find operations, N
insert operations, (logN)1/2 delete operations, and
(logN)1/2 decrease-key operations on a set of data
items with keys drawn from a linearly ordered set .
For a delete operation, a pointer is provided to the
record that must be deleted. For the decrease-key
operation, a pointer is provided to the record that
has its key decreased. Which one of the following
data structures is the most suited for the algorithm
to use, if the goal is to achieve the best total
asymptotic
complexity
considering
all
the
operations?

(a)Unsorted array
(b)Min - heap
(c)Sorted array
(d)Sorted doubly linked list ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2017 · Set 2 · MCQ · 2 marksQ8 · page 11 of the book

Consider the C program fragment below which is
meant to divide x by y using repeated subtractions.
The variables x, y, q and r are all unsigned int.
while (r >= y) {
     r = r - y;
     q = q + 1;
}

Which of the following conditions on the variables x,
y, q and r before the execution of the fragment will
ensure that the loop terminates in a state satisfying the
condition x == (y*q + r)?

(a)(q = = r) && (r = = 0)
(b)(x > 0) && (r = = x) && (y > 0)
(c)(q = = 0) && (r = = x) && (y > 0)
(d)(q = = 0) && (y > 0)

GATE 2016 · Set 2 · MCQ · 2 marksQ9 · page 12 of the book

The following function computes XY for positive
integers X and Y.
int exp (int X, int Y) {
    int res = 1;
 int a = X;
 int b = Y;

while ( b != 0 ){
if ( b%2 == 0)
{
a = a*a;
b = b/2;

}
else{
res = res*a;
b = b-1;
}
 }
 return res;
 }
Which one of the following conditions is TRUE before
every iteration of the loop?

(a)XY = ab
(b)(res * a)Y = (res * X)b
(c)XY = res * ab
(d)XY = (res * a)b

year not read yetQ11 · page 12 of the book

Consider the following pseudo code. What is the total
number of multiplications to be performed?
D = 2
for i = 1 to n do
  for j = i to n do
      for k = j + 1 to n do
          D = D * 3

(a)Half of the product of the 3 consecutive integers.
(b)One-third of the product of the 3 consecutive integers.
(c)One-sixth of the product of the 3 consecutive integers
(d)None of the above.

GATE 2013 · MCQ · 2 marksQ13 · page 12 of the book

Consider the following function:
int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i<= n; i++)
        for (j = 2; j <= n; j = j * 2)
k = k + n/2;
    return k;
}
The return value of the function is__

(a)Θ(n2)
(b)Θ(n2 log n)
(c)Θ(n3)
(d)Θ(n3 log n)

GATE 2007Q15 · page 13 of the book

Consider the following segment of C-code:

int j, n;

j = 1;

while (j <= n)

j = j * 2;

The number of comparisons made in the execution of
the loop for any n>0 is:

(a)⌈log2 n⌉ + 1
(b)n
(c)⌈log2 n⌉
(d)⌊log2 n⌋ + 1

Self-check

Question 1

What is the order of the number of executions of c++ in for (i = 1; i <= n; i *= 2) for (j = 1; j <= i; j++) c++;?

Show answer

$\Theta(n)$ : the inner counts form the geometric series $1 + 2 + 4 + \cdots + n \approx 2n$ .

Question 2

How many times does the body of for (i = 2; i < n; i = i * i) run, in order of magnitude?

Show answer

$\Theta(\log \log n)$ : $i$ takes the values $2, 4, 16, 256, \ldots = 2^{2^j}$ .

Question 3

A recursive function calls itself once with $n - 1$ and does constant work otherwise. What are its time and its stack space?

Show answer

$\Theta(n)$ time and $\Theta(n)$ stack space (depth $n$ ).

Question 4

An algorithm runs in time proportional to the value $n$ of its numeric input. Is it polynomial time?

Show answer

No: if $n$ has $b$ bits, the time is about $2^b$ , exponential in the input length (pseudo-polynomial).

Revision card

One-screen revision

Count the dominant operation as a sum over the loops; keep the order, drop constants.
Nested independent: multiply; dependent: sum; *= 2: log; j += i: harmonic; doubling inner bound: geometric, $\Theta(n)$ .
Worst, best, average are different functions; space includes the recursion stack.
Loops to the value $n$ are exponential in the bit length.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition), Chapter 2 Getting Started (analysing algorithms) and Appendix A (summations)
·Kleinberg and Tardos, Algorithm Design, Chapter 2 Basics of Algorithm Analysis

Verification

The five loop nests of the table were compiled and run (cc -std=c11) and each measured count equals its closed form for all five values of n; the closed forms were rechecked for n = 1 to 200 by a second implementation in Python, and the C program printed on this page is asserted to be the program that produced the table (scripts/enum-checks/algo_analysis.py). The six loop nests of the worked examples were counted by simulation and their closed forms confirmed for all tested n. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (loop counts, recurrences, merge and quicksort counts and averages, hash probes and load-factor formulas, DP tables, MST and shortest-path runs, Floyd matrices); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Asymptotic notation

Solving recurrences: substitution, tree and Master theorem