SICP Exercise 1.26
n. The number of steps for iterative
process can be expressed by recurrency \(T(n)=T(n/2)+O(1)\), with
Louis replaced fast iterative process with recursive one, that
splits in two branches for even
n. This corresponds to different
recurrency \(T(n)=2 T(n/2)+O(1)\), with solution \(O(n)\).