Complexity Quiz: Easy

EditorialUpdated Oct 31, 2026

Complexity Quiz: Easy

Fifteen pieces of code: single loops, nested loops, halving and doubling, two inputs, memory and a library sort. For each, pick its growth. 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.

1 / 15

Multiple choice

What is the time complexity of this loop?

long long count = 0;
for (int i = 0; i < n; i++)
    count++;

Multiple choice

In simplest form, what is the time complexity of these two loops?

long long count = 0;
for (int i = 0; i < n; i++)
    count++;
for (int j = 0; j < n / 2; j++)
    count++;

Multiple choice

The inner loop only runs up to i. What is the time complexity?

long long count = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

Multiple choice

The grid has n rows and m columns. What is the time complexity?

long long count = 0;
for (int i = 0; i < n; i++)       // n rows
    for (int j = 0; j < m; j++)   // m columns
        count++;

Multiple choice

How do the comparisons a library sort makes grow with n?

long long count = 0;
sort(nums.begin(), nums.end(), [&](long long a, long long b) {
    count++;                    // each comparison the sort asks for
    return a < b;
});