Use python to solve the following and please give a detailed

Use python to solve the following and please give a detailed solution.

Solve the following recurrence relations and give a bound for each of them. T (n) = T(n - 1) + e^n, where c> 1 is some constant T(n) = T(n - 1) + n^c, where c greaterthanorequalto 1 is a constant T(n) = 49T(n/25) + n^3/2 log n

Solution

1. T(n)=T(n-1)+cⁿ

solution - T(n-1)=T(n-2)+c^(n-1) and so on..

so cⁿ is the upper bound, every term is asymptotically smaller than cn

T(n)=(cⁿ)

For question 2 and 3--

Master\'s theorem solves the recurrence relations of type T(n)=aT(n/b)+f(n) . In this 3 cases are formed.

Case 1: if f(n)=O(n^c) and where c<log_ba

Case 2: f(n)=(n^clogn) where c=log_ba

Case 3:f(n)=(n^c) where c>log_ba

So we calculated log_ba and compared with c which you will get when you write f(n) as asymptotic notation then decide the case and use the master\'s theorem result.

2.T(n)=T(n-1)+n^c

solution - Applying master\'s theorem log_ba=0 where a=1 and c> log_ba

so T(n)= (n^c)

3.T(n)=49T(n/25)+n^3/2logn

solution - Applying master\'s theorem f(n)=omega(n^3/2) , c=3/2

so c>log₂₅49

T(n)=(n^3/2logn)