Answer:
To solve the recurrence relation T(n)=T(n-1)+T(n/2)+n, we can use the recursion tree to guess the asymptotic upper bound . There are two branches T(n-1) and T(n/2) respectively. The depth of the T(n-1) branch will be n-1, and the depth of the T(n/2) branch will be log_2(n). At each level, there is an additional cost of n. Therefore, the cost at each level is n+1, and the total cost of the tree will be roughly:
n + (n+1) + (n+1)^2 + ... + (n+1)^(log_2(n)-1) + (n+1)^(n-1)
This is a geometric series, so we can use the formula for the sum of a geometric series to get:
(n+1)^(log_2(n)) - 1 / (n+1) - 1
= (n+1)^log_2(n) / (n+1) - 1
= n^log_2(n) / (n+1) + O(1)
Therefore, the asymptotic upper bound is O(n^log_2(n)).
To confirm this using the substitution method, we assume that T(k) <= ck^log_2(k) for all k < n, and we want to show that T(n) <= cn^log_2(n). We have:
T(n) = T(n-1) + T(n/2) + n <= c(n-1)^log_2(n-1) + c(n/2)^log_2(n/2) + n
<= c(n-1)^log_2(n) + cn^log_2(n)/2 + n
= cn^log_2(n) - c(n-1)^log_2(n)/n + n
<= cn^log_2(n)
Therefore, we have shown that T(n) is O(n^log_2(n)), which confirms our guess from the recursion tree.
Step-by-step explanation: