Complexity Quiz: Hard
Editorial
Complexity Quiz: Hard
Fifteen pieces of code: searches through subsets and orderings, remembered answers, divide and conquer past the easy cases, amortized costs, and a loop that runs log log n times. 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: Hard
1 / 15Multiple choice
What is the time complexity of this
fib?long long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}Multiple choice
The same
fib, remembering each answer once it's worked out. What is its time complexity?vector<long long> memo(MAX_N + 1, -1);
long long fib(int n) {
if (n <= 1) return n;
if (memo[n] < 0) memo[n] = (fib(n - 1) + fib(n - 2)) % 1000000007;
return memo[n];
}Multiple choice
Each value is left out, then taken. How many subsets does this reach, as n grows?
vector<int> chosen;
function<long long(int)> subsets = [&](int i) -> long long {
if (i == n) return 1; // one subset finished
long long without = subsets(i + 1);
chosen.push_back(i);
long long withIt = subsets(i + 1);
chosen.pop_back();
return without + withIt;
};
long long count = subsets(0);Multiple choice
This puts n values in every possible order. How many orderings does it finish, as n grows?
vector<bool> used(n, false);
function<long long(int)> arrange = [&](int placed) -> long long {
if (placed == n) return 1; // one ordering finished
long long total = 0;
for (int i = 0; i < n; i++)
if (!used[i]) {
used[i] = true;
total += arrange(placed + 1);
used[i] = false;
}
return total;
};
long long count = arrange(0);Multiple choice
What is the time complexity of
three(n)?long long three(int n) { // n steps of its own, then three half-size calls
if (n <= 1) return 1;
return n + three(n / 2) + three(n / 2) + three(n / 2);
}Multiple choice
Euclid's GCD, given two numbers up to n (its slowest pair, neighbouring Fibonacci numbers). How does it grow?
long long count = 0;
while (b != 0) {
long long t = a % b;
a = b;
b = t;
count++;
}Multiple choice
i is squared on every pass. What is the time complexity?
long long count = 0;
for (long long i = 2; i < n; i = i * i)
count++;Multiple choice
For each i, the inner loop runs up to the square root of i. What is the time complexity?
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j * j < i; j++)
count++;Multiple choice
An array doubles when full. How do its copies grow over n appends, in total?
long long count = 0; // values copied
long long capacity = 1, size = 0;
for (int i = 0; i < n; i++) {
if (size == capacity) {
count += size;
capacity *= 2;
}
size++;
}Multiple choice
This array grows by 100 slots when full. How do its copies grow over n appends, in total?
long long count = 0; // values copied
long long capacity = 100, size = 0;
for (int i = 0; i < n; i++) {
if (size == capacity) {
count += size;
capacity += 100;
}
size++;
}Multiple choice
A queue made of two stacks: n enqueues, then n dequeues. How do its steps grow in total?
vector<int> inbox, outbox;
long long count = 0;
for (int i = 0; i < n; i++) {
inbox.push_back(i);
count++;
}
for (int i = 0; i < n; i++) {
if (outbox.empty())
while (!inbox.empty()) {
outbox.push_back(inbox.back());
inbox.pop_back();
count++;
}
outbox.pop_back();
count++;
}Multiple choice
The inner loop starts at i and jumps by i + 1. What is the time complexity?
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j += i + 1)
count++;Multiple choice
What is the time complexity of
peel(n)?long long peel(int n) { // n steps, then the same on one fewer
if (n == 0) return 0;
long long steps = 0;
for (int i = 0; i < n; i++) steps++;
return steps + peel(n - 1);
}Multiple choice
sq does n² steps, then two half-size calls. What is its time complexity?long long sq(int n) { // n² steps, then 2 half-size calls
if (n <= 1) return 1;
long long steps = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) steps++;
return steps + sq(n / 2) + sq(n / 2);
}Multiple choice
The same
sq, with four half-size calls. What is its time complexity?long long sq(int n) { // n² steps, then 4 half-size calls
if (n <= 1) return 1;
long long steps = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) steps++;
return steps + sq(n / 2) + sq(n / 2) + sq(n / 2) + sq(n / 2);
}