Solving T(n) = T(n/2) + 1

Each recursive call halves the problem size while doing constant extra work.

Count how many times $n$ can be halved before reaching a constant size.

1. 1. Count the recursion depth

   The problem size halves at each level, so after $k$ levels the size is $n/2^k$; recursion stops once this reaches a constant.

   $$n/2^k=O(1)⟹k={\log }_{2}n$$

2. 2. Sum the constant work per level

   Each of the $O(\log n)$ levels does $O(1)$ work, giving total time $O(\log n)$.

Answer: O(log n)