Complexity Quiz: Medium
Editorial
Complexity Quiz: Medium
Fifteen pieces of code that look slower or faster than they are: loops that shrink, loops that jump, library calls that hide a loop, simple recursions, and a sort's best and worst inputs. Every answer was checked by running the code on our judge in C++, Python, Java and JavaScript at three sizes of n, 1,000, 2,000 and 4,000 unless the answer names others: the four counted the same steps, and the growth in the answer fitted those counts best. Where the cost hides inside a library call, every language's times were checked instead.
Complexity Quiz: Medium
1 / 15Multiple choice
The inner loop jumps by i. What is the time complexity?
long long count = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < n; j += i)
count++;Multiple choice
The inner loop runs n times, then n is halved. What is the time complexity?
long long count = 0;
while (n > 0) {
for (int j = 0; j < n; j++)
count++;
n = n / 2;
}Multiple choice
For each i, j doubles until it reaches i. What is the time complexity?
long long count = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j *= 2)
count++;Multiple choice
A loop of n finds each value's position in a list of n. What is the time complexity?
long long count = 0;
for (int x = 0; x < n; x++) // items: a vector of n values
if (find(items.begin(), items.end(), x) != items.end()) count++;Multiple choice
The loop asks for the largest value on every pass. What is the time complexity?
long long count = 0;
for (int i = 0; i < n; i++) // nums: n values
if (*max_element(nums.begin(), nums.end()) == n - 1) count++;Multiple choice
What is the time complexity of
f(n)?long long f(int n) {
if (n == 0) return 1;
return 1 + f(n - 1);
}Multiple choice
g scans n values, then recurses on half. What is its time complexity?long long g(int n) {
if (n == 0) return 0;
long long steps = 0;
for (int i = 0; i < n; i++) steps++; // n steps
return steps + g(n / 2);
}Multiple choice
h scans n values, then recurses on both halves. What is its time complexity?long long h(int n) {
if (n <= 1) return 1;
long long steps = 0;
for (int i = 0; i < n; i++) steps++; // n steps
return steps + h(n / 2) + h(n - n / 2);
}Multiple choice
Two indexes start at the ends and one moves inward each step. What is the time complexity?
long long count = 0;
int i = 0, j = n - 1;
while (i < j) {
if ((i + j) % 3 == 0) i++;
else j--;
count++;
}Multiple choice
nums holds n small values. What is the time complexity of this window?long long count = 0;
int left = 0, total = 0;
for (int right = 0; right < n; right++) {
total += nums[right];
while (total > 20) {
total -= nums[left++];
count++;
}
count++;
}Multiple choice
What is the time complexity of these three loops?
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
for (int k = 0; k < j; k++)
count++;Multiple choice
The inner loop only runs when i is a power of 2. What is the time complexity?
long long count = 0;
for (int i = 1; i <= n; i++) {
count++;
if ((i & (i - 1)) == 0) // i is a power of 2
for (int j = 0; j < n; j++)
count++;
}Multiple choice
Bubble sort stops early when a pass swaps nothing. How does it grow on input that is already sorted?
long long count = 0;
bool swapped = true;
for (int passes = 0; swapped; passes++) {
swapped = false;
for (int i = 0; i < n - 1 - passes; i++) {
count++;
if (nums[i] > nums[i + 1]) {
swap(nums[i], nums[i + 1]);
swapped = true;
}
}
}Multiple choice
The same bubble sort, given values in reverse order. How does it grow?
long long count = 0;
bool swapped = true;
for (int passes = 0; swapped; passes++) {
swapped = false;
for (int i = 0; i < n - 1 - passes; i++) {
count++;
if (nums[i] > nums[i + 1]) {
swap(nums[i], nums[i + 1]);
swapped = true;
}
}
}Multiple choice
Given an n by n grid, this loop reads its diagonal. What is its time complexity?
long long count = 0;
for (int i = 0; i < n; i++)
count += 1 + grid[i][i]; // grid: n by n, all zeros