Structures and performance

JavaScript · Unit 21: Complexity

A program's label doesn't depend only on your loops: it depends on where you keep the data.

includes checks the array one by one, O(n). A Set is built to answer in one go, O(1).

const seen = new Set([4, 9, 1]);
console.log(seen.has(9));
console.log(seen.has(7));
const items = [4, 9, 1];
console.log(items.includes(9));

Prints

true
false
true

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
The 3 is at the front of the array; the 5 isn't there at all. What does it print?
2. Multiple choice
Which one answers just as fast with 10 items as with 10,000?
3. Complete the code
Complete it to find out how many different values there are.
4. Predict the output
The array carries a repeated value. What does it print?
5. Find the bug
It should count how many items had already shown up before (here, one). Which line has the error?
6. Put the lines in order
Count how many of the names on the list are allowed.
7. Predict the output
It counts the calls to fib with 5 and with 15. What does it print?
8. Multiple choice
These are the labels the app puts on every challenge. Which list goes from cheapest to most expensive?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.