Question

Int someFct (int N)[

if (N <=2) {return 0;}
if (%2==0) [return (5+somedFct (N/2));}
else {return (4*someFct (N-3));}
}
a) (5) Show tree of fct for N = 7?
b) Give the recurrence formula for the above code.
Base case(s) formula:


Recursive case recurrence formula as derived directly from the code. You should get a somewhat weird recurrence. Do NOT try to solve it. Hint: how do you write the function expression for absolute value of any real number x (|x| = ......)?

Answer 1

solution attached.

Step-by-step explanation:

Also, the tetha time complexity of T_upper would be
`2^{(n)/(3) }`