Big-O growth

What the problems look like

A few statements from this skill. Answers, hints and worked solutions live in the practice session.

1. Warm-up

   A loop starts with $n = 32$ (a power of two) and repeatedly replaces $n$ with $\lfloor n/2 \rfloor$, stopping as soon as $n = 1$, incrementing a counter on each pass. How many times does the loop body execute? (This is why halving until $1$ takes $\Theta(\log n)$ time.)

2. Warm-up

   A loop starts with $n = 2048$ (a power of two) and repeatedly replaces $n$ with $\lfloor n/2 \rfloor$, stopping as soon as $n = 1$, incrementing a counter on each pass. How many times does the loop body execute? (This is why halving until $1$ takes $\Theta(\log n)$ time.)

3. Warm-up

   A loop starts with $n = 1024$ (a power of two) and repeatedly replaces $n$ with $\lfloor n/2 \rfloor$, stopping as soon as $n = 1$, incrementing a counter on each pass. How many times does the loop body execute? (This is why halving until $1$ takes $\Theta(\log n)$ time.)

Problems shown under their original terms: Generated (template, solver-computed).