0
Challenge · 17Cost: Time and Space

Counting steps

Complexityused in ~100% of apps

You have already felt this. You measured a loop taking 3,861 milliseconds and another doing the same job in 1. Now you get the tool that lets you predict that before you run anything.

Core idea. Count how many times the innermost line runs, as a formula in terms of the input size. That count, not the seconds on your machine, is what decides whether your solution finishes in time.
Playground, this isn't a screenshot
count the innermost line, for a list of n items
total = total + 1;on its own1runs once, whatever n is
for (const x of a) total += x;one loopnonce per item
for (i) for (j) count++;loop inside a loopn x nevery pair
for (i) for (j = i+1) count++;each pair oncen x n / 2half the work, same shape
for (const x of a) seen.includes(x);hidden inner loopn x nincludes walks the list
↑ play a little first, then dig in