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

= T(n) = 1 for n < 50

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

Step-by-step 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