Let n be a positive integer and f(n) = 0 if n = 1, and f(n) = f(⌊n/2⌋) + 1 if n > 1. What is f(25), and what does the function compute?

1. A4, ⌊log₂ n⌋
2. B14, ⌊log₂ n⌋
3. C4, ⌊n/2⌋
4. D14, ⌊n/2⌋

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. 4, ⌊log₂ n⌋

Explanation

f(25) = f(12) + 1 = f(6) + 2 = f(3) + 3 = f(1) + 4 = 4. Halving until 1 counts the halvings, i.e. ⌊log₂ n⌋.