O(1) and O(n)

JavaScript · Unit 21: Complexity

Some jobs cost the same whatever n is. Adding 1 + 2 + … + n with the formula is one single calculation, with n = 5 and with n = 5000.

We call that O(1), and you read it "order one".

function steps(n) {
  let s = 0;
  const total = (n * (n + 1)) / 2;
  s++;
  return s;
}
console.log(steps(5), steps(5000));

Prints

1 1

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 counter counts the slots first looks at. What does it print?
2. Multiple choice
Which of these costs more as the array grows?
3. Predict the output
Here each turn costs two steps, and there is one before it starts. What does it print?
4. Multiple choice
A function does 3n + 5 steps. How is its cost written?
5. Complete the code
Complete it so last gives the final item in one single step.
6. Find the bug
lookFor should say whether the value is there, and s how many items it looked at. Which line has the error?
7. Put the lines in order
Count how many items you look at until you bump into the 8.
8. Predict the output
Both ways add up 1 + 2 + … + 100. What does it print?

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