Question

Design a recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns the total number of 1’s in n’s binary representation. Note that the input is n, not its binary representation. For example, A(9) should return 2 as 9’s binary representation is 1001, while A(7) should return 3 since 7 is 111 in binary. Note that your algorithm should have a running time of O(log n). Justify your answer. You need to do the following: (1) give a description of your algorithm in English or high-level pseudo-code; and (2) give its analysis, ie. recurrence equation and its solution.

Answer 1

Recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns the total number of 1’s in n’s binary representation.

int A(int n)
{
   if(n==0)
   {
       return 0;
   }
   if(n%2==0)
       return 0 + A(n/2);
   return 1 + A(n/2);
}
The algorithm checks keeps on checking the last bit of the number, if the number is odd then add 1 to count and right n by 1 bit, i.e dividing n by 2 until n is zero, and call the A function after each shift.

The recurrence relation is