NOTE_C/DS_1_30

Question

Consider the following program:

void ME(int n)

{

          printf(“*”);

          if(n>1)

          {

                    ME(n/4);

                    ME(n/4);

                    ME(n/4);

                    ME(n/4);

          }

}

lets X be the number of asterisks printed by the above function when n=1024. Then the value of X will be___________.

(Hint: take n as a power of 4)

Comments

ME(n) =  4ME(n/4) +1  ,n>1

           =  1                     ,n=1

 

M[4] = 4*M[1] + 1

       = 4 + 1  ==> 5.

M[16] = 4 *M[4] + 1

          = 4*5 + 1 ==> 21

M[64] = 4*M[16] + 1

        = 4*21+1 ==> 85

M[256] = 4*M[64] + 1

             = 4*85 + 1 ==> 341

M[1024] = 4*341 + 1 ==> 1365.

Answer 1365.

 

---

it will be O(n) but for solving recurrences precisely, there is a procedure right?

---

One thing is important here, For n = 2 n=3 Also the answer will be 5.