Example 5

void p (int n)
{
  if (n < 6) printf("Done!\n");
  else { printf("n = %d\n",n);
         p(n/2); }
}

Recursive algorithms often succumb to the same analysis methods used for loops.

O(Program) = (# executions of P) * O(1)

= O(log N)