Question

Write the recurrence relation for the following program fragment, assuming somethingElse(n) requires constant amount of work. You don’t have to solve this recurrence relation.int something (int n) { if (n < 50) { System.out.println("!"); return n+10;else { return something(n-1) + somethingElse(n);

Answer 1

Answer:

 = T(n) = 1  for n < 50

  = T(n) = T(n-1) + 1 for  n >= 50

Explanation:

The Given program fragment is :

int something (int n) {

if (n < 50) {

       System.out.println("!");

return n+10;

else {

    return something(n-1) + somethingElse(n);

  }

}

The recurrence relation for the program fragment above can be expressed as :

      = T(n) = 1  for n < 50

also T(n) = T(n-1) + 1 for  n >= 50