"What is the time complexity of this loop?" recurs across GATE, ISRO, UGC NET and state-PSC papers. Wrong answers usually come from assuming two loops mean n squared instead of counting iterations. Attempt these 12 previous-year questions first. About 60 questions are available for practice under Iterative Loops & Code. Course PYQs link to exact solutions; find the ISRO and TPSC questions through the Algorithms learn module.
Warm-up: a doubling loop contributes log n
Count body executions, then multiply only for independent loops. Doubling from 1 through n takes ⌊log₂n⌋ + 1 passes. For broad practice across growth rates, loops and recurrences, use Time Complexity MCQs: 12 solved questions on asymptotic analysis. Three GATE questions recur below because each exposes a different loop trap: independent counts multiply, dependent step sizes sum and accumulated values require a trace.
Q1. ISRO 2020
What is the complexity of the following code?
sum = 0;
for (i = 1; i <= n; i *= 2)
for (j = 1; j <= n; j++)
sum++;(a) O(n²) (b) O(n log n) (c) O(n) (d) O(n log n log n)
Answer: (b). The outer values 1, 2, 4, ... give ⌊log₂n⌋ + 1 passes. The inner loop runs n times per pass, so total work is n(⌊log₂n⌋ + 1) = Θ(n log n). Two n-length loops would give n².
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) ⌈log n⌉ + 2 (b) n (c) ⌈log n⌉ (d) ⌊log n⌋ + 2
Base of Log is 2 in all options.
Answer: (d). For n = 8, j is tested at 1, 2, 4, 8, then 16: 5 comparisons, and ⌊log₂8⌋ + 2 = 3 + 2 = 5. For n = 5, tests at 1, 2, 4, 8 give 4. Option (a) gives ⌈log₂5⌉ + 2 = 5, but (d) gives ⌊log₂5⌋ + 2 = 2 + 2 = 4.
Trace questions: the loop computes a value
For a final variable value, trace assignments in order.
Q3. ISRO 2007
Consider the following pseudo-code
x:=1;
i:=1;
while (x <= 1000)
begin
x:=2^x;
i:=i+1;
end;What is the value of i at the end of the pseudo-code?
(a) 4 (b) 5 (c) 6 (d) 7
Answer: (b). From x = 1, i = 1, the passes produce (x, i) = (2, 2), (4, 3), (16, 4), (65536, 5). Since 65536 > 1000, i ends at 5. The test precedes the overshooting pass.
Consider the following pseudo-code fragment, where a and b are integer variables that have been initialized:
/* Pre-conditions : (a>1 ∧ a<b) */
/* Assume that overflow never occurs */
int x=0; int p=1;
while (p<b){
p=p*a;
x=x+1;
}When the while loop terminates, what will be the value of x in terms of a and b?
(a) a^b (b) b^a (c) ⌊log_a b⌋ (d) ⌈log_a b⌉
Answer: (d). After x passes, p = a^x. It stops at the first a^x >= b, so x = ⌈log_a b⌉. For a = 2, b = 10, p goes 1, 2, 4, 8, 16 and x ends at 4. Indeed, ⌈log₂10⌉ = ⌈3.32⌉ = 4, not the floor value 3.
Half ranges and doubled counters together
A range from n/2 through n still has Θ(n) iterations.
Q5. ISRO December 2017
Consider the program
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}The complexity of the program is
(a) O(log n) (b) O(n²) (c) O(n² log n) (d) O(n log n)
Answer: (d). The outer loop runs roughly n/2 + 1 = Θ(n) times. The inner takes ⌊log₂n⌋ + 1 = Θ(log n) passes. Their product is Θ(n log n).
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) Θ(n²) (b) Θ(n² log n) (c) Θ(n³) (d) Θ(n³ log n)
Answer: (b). About (n/2 + 1)⌊log₂n⌋ passes each add n/2. Thus k ≈ (n/2)(log₂n)(n/2) = (n²log₂n)/4 = Θ(n² log n). Running time is only Θ(n log n); the extra factor comes from the accumulated value.
When the inner loop shrinks with the outer
When an inner bound depends on the outer variable, sum its work. Geometric n + n/2 + ... stays below 2n; harmonic n/1 + n/2 + ... + n/n equals nH_n = Θ(n log n).
Q7. TPSC Senior Computer Assistant 2024
What is time complexity of fun()?
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}(a) O(n²) (b) O(n*log(n)) (c) O(n) (d) O(n*log (n*log(n)))
Answer: (c). For n = 16, work is 16 + 8 + 4 + 2 + 1 = 31, below 2n = 32. Generally, n + n/2 + n/4 + ... + 1 < 2n, so total work is O(n), not O(n log n).
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) Θ(n²) (c) Θ(n log n) (d) Θ(n² log n)
Answer: (c). For fixed i, the inner loop runs about n/i times. Total work is n/1 + ... + n/n = nH_n = Θ(n log n). For n = 8, exact counts are 7 + 4 + 3 + 2 + 2 + 2 + 1 + 1 = 22, close to 8H_8 ≈ 8 × 2.72 = 21.76.
What value does the loop leave behind?
For an accumulated value, read the update before counting rounds.
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) = Θ(log n) (b) val(j) = Θ(√n) (c) val(j) = Θ(n) (d) val(j) = Θ(n log n)
Answer: (c). Each update halves i, then adds the new i. For n = 16, i becomes 8, 4, 2, 1, 0 while j becomes 8, 12, 14, 15, 15. Thus j = 15. Generally, j = n/2 + n/4 + ... + 1, with integer rounding, so j = Θ(n).
Worst case, best case, and exact counting
Early exits split upper and lower bounds. Exact counts need a closed form and small-input check. See MCQ, MSQ or NAT? GATE Question Types Explained for the response formats.
Consider the following C code segment:
int IsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Prime\n"); return 0;}
return 1;
}Let T(n) denotes 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) = Ω(1)
(c) T(n) = O(n) and T(n) = Ω(√n)
(d) None of the above
Answer: (b). Prime n takes about √n - 1 iterations, so T(n) = O(√n). Even n returns at i = 2, so T(n) = Ω(1). That constant case breaks option (a)'s Ω(√n) claim.
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.
Answer: (c). Count triples with 1 <= i <= j < k <= n: C(n + 1, 3) = (n - 1)n(n + 1)/6. For n = 3, (i, j) = (1, 1) gives 2 choices for k; (1, 2) and (2, 2) give 1 each. Total = 2 + 1 + 1 = 4, matching 2 × 3 × 4/6 = 4. The consecutive integers are n - 1, n, n + 1.
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) n² (b) n(log n)² (c) n log n (d) n log(log n)
Answer: (d). The middle loop makes p = ⌊log₂n⌋. The third adds ⌈log₂p⌉ = Θ(log log n) per outer pass, so q ≈ (n - 1)log₂(log₂n) = Θ(n log log n). For n = 1024, p = 10; k takes 1, 2, 4, 8, adding 4 on each of 1023 passes. Thus q = 1023 × 4 = 4092.
The short version and your next step
A doubling or halving counter gives log n passes.
Multiply loop counts only when their bounds are independent. Otherwise sum the work: geometric series stay linear, while harmonic series give n log n.
A range from n/2 through n is still Θ(n).
Return-value questions count what accumulates, not merely how many rounds run.
Early exits can split the O upper bound from the Ω lower bound.
Every GATE PYQ above is solved inside GATE Guidance by Sanchit Sir. Identify your weak pattern, browse the GATE CS preparation options, then practise a focused set.
