For Time Complexity of recursive programs
we only consider the statements which call the function again and again
so, in the statement below
return(5A(n/2)+3A(n/2)+MA(n))
Now above expression means 5 times of A(n/2) + 3 times of A(n/2) + MA(n)
now how many times our function A(n) has been called again and with what subproblem sizes?
(1) First with sub-problem size of n/2 whose result is to be multiplied by 5.
(2) Second again with the sub-problem size of A(n/2) with the result multiplied by 3.
The recurrence for this program is
2T(n/2) + O($n^2$)(This is complexity if MA(n)) which evaluates to $\theta(n^2)$ by master's theorem.
$n^{\log _b a} = n^{\log _2 2}=n$
and f(n)=$O(n^2)$
This is for time complexity.
And for the value , we need to consider what exact value the program will return at each step
So for the statement
return(5A(n/2)+3A(n/2)+MA(n))
we take into account constants 5 and 3 when we are calling function A(n)
So value recurrence relation is :
5T(n/2) + 3T(n/2) +MA(n) = 8T(n/2) + MA(n) if n>1
$n^2 -n+1$ if n<=1.
