Big-O Complexity Quiz
Four short prompts on identifying time complexity from JavaScript code: nested loops, halving, recursion, and a bug-by-complexity hunt.
Question Bank
Easy
JavaScript
4 questions
big-o
asymptotic-analysis
quiz
fundamentals
1,137 views
11
What is the time complexity of this function and why?
Examples
Example 1:
Input: f(3)
Output: inner body executes 3 * 3 = 9 times
Explanation: Two nested loops over n give n^2 iterations. f(6) runs 36 iterations, confirming the quadratic shape. Time O(n^2), space O(1).function f(n) {
let sum = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
sum += i * j;
}
}
return sum;
}What is the time complexity of this function in terms of n and why?
Examples
Example 1:
Input: f(8)
Output: 3
Explanation: 8 -> 4 -> 2 -> 1 takes 3 halving steps. f(1024) returns 10 (since 2^10 = 1024). The loop runs about log_2(n) times, hence O(log n).function f(n) {
let count = 0;
while (n > 1) {
count++;
n = Math.floor(n / 2);
}
return count;
}Write the smallest implementation of fibonacci(n) you can think of, then state its time complexity. After that, sketch the linear-time fix.
Spot the complexity bug. The function below is supposed to be O(n) but is actually slower. Identify the line that ruins the complexity.
Examples
Example 1:
Input: words = ['a', 'b', 'c']
Output: 'abc' in either version
Explanation: Repeated string concatenation can be O(n^2) under the naive allocate-and-copy model. Modern V8 amortizes via rope strings, but to guarantee O(n) across engines, push to an array and join('') at the end.function buildMessage(words) {
let out = '';
for (let i = 0; i < words.length; i++) {
out = out + words[i];
}
return out;
}