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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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 isfor (const x of a) total += x;one loopnonce per itemfor (i) for (j) count++;loop inside a loopn x nevery pairfor (i) for (j = i+1) count++;each pair oncen x n / 2half the work, same shapefor (const x of a) seen.includes(x);hidden inner loopn x nincludes walks the list↑ play a little first, then dig in