Skip to the content
Start

O(log n)

JavaScript · Unit 21: Complexity

There is something better than looking at everything: throwing half of it away on each step.

Halving 8 down to 1 takes 3 steps; halving 1024, only 10. That is O(log n).

function halvings(n) {
  let s = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    s++;
  }
  return s;
}
console.log(halvings(8));
console.log(halvings(1024));

Prints

3
10

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. 1. Predict the output

    The second number is twice the first one. What does it print?

  2. 2. Put the lines in order

    Count how many times 64 can be halved before it reaches 1.

  3. 3. Complete the code

    Complete it so the counter counts the halvings of 100.

  4. 4. Multiple choice

    You have 1000 names sorted from A to Z. If each try throws away half of them, how many names do you look at in the worst case?

  5. 5. Find the bug

    stepsUpTo(n) should count how many times you have to double 1 to reach n. With 1000 it should give 10. Which line has the error?

  6. 6. Find the case that fails

    halvings(n) should say how many times n can be halved, always keeping the whole part, until it reaches 1. halvings(1) is 0. Which call does it fail with?

  7. 7. Predict the output

    The inner loop halves m. What does it print?

  8. 8. Predict the output

    This one first does a halving job and then a full walk. What does it print?

Do this lesson

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

See all lessons →