What this topic covers
14 subtopics- Counting operations6
- Logarithmic loops6
- Loops6
- Notation4
- Recurrences4
- Best, average and worst case3
- Nested loops3
- Recursion3
- Space complexity3
- Amortised analysis2
- Master theorem2
- Choosing an algorithm1
Show all 14 subtopics
- Hidden costs1
- Lower bounds1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
Complexity questions appear in almost every placement test and in GATE. The trick is to count how many times the innermost statement runs as a function of n, keep the fastest-growing term and drop constants. Loops that halve or double a variable give log n; a loop inside a loop multiplies; recursion gives a recurrence. Where a question asks for an exact count, the program shown was compiled and run to produce the answer.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
What is the time complexity of this function?
def total(arr):
s = 0
for x in arr:
s += x
return sShow answer and explanation
Explanation
The loop body runs once per element, so the work grows linearly with the length n of the array.
Why the other options are wrong
- BThere is no inner loop.
- CNothing is halved; every element is visited.
- DThe work depends on the input size.
What is the time complexity of this loop?
while n > 1:
n = n // 2Show answer and explanation
Explanation
Each step halves n, so it reaches 1 after about log₂ n steps. Any loop whose variable is multiplied or divided by a constant is logarithmic.
Why the other options are wrong
- BThe number of steps grows with n.
- Cn is halved, not decreased by 1.
- DO(n/2) is just O(n), and it is still not the halving count.
Binary search runs on a sorted array of 1024 elements. What is the maximum number of iterations (middle elements compared) for any key, present or absent?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
The worst case is ⌊log₂ n⌋ + 1 = 10 + 1 = 11: ten halvings bring 1024 candidates down to 1, and that last candidate still has to be compared.
What is the time complexity?
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j *= 2) {
count++;
}
}Show answer and explanation
Explanation
The outer loop runs n times and the doubling inner loop runs about log₂ n times for each: n × log n.
Why the other options are wrong
- AThe inner loop adds a log factor.
- BThe outer loop is linear.
- Cj doubles, so the inner loop is logarithmic.
Solve T(n) = 8T(n/2) + n².
Show answer and explanation
Explanation
a = 8, b = 2, so n^(log_b a) = n³. f(n) = n² is polynomially smaller (case 1), so the leaves dominate: Θ(n³). This is the naive divide-and-conquer matrix multiplication.
Why the other options are wrong
- AThe eight subproblems outweigh the n² combining work.
- BCase 2 needs f(n) = Θ(n³).
- Clog₂ 8 = 3, not 8.