Using masters Algorithm or most appropriate methods how to solve the following Recurrence: 1) T(n)=T(n/2)+1

2) T(n)=T(n/2)+ n^2/2 +n

1) Using Masters Theorem for Dividing Functions: T(n)=aT(n/b)+f(n). f(n)=Theta(n^k.logn^p). Here, log(a) to the base b is equal to 0. Also, k=0 and p=0. Thus, log(a) to base b=k and p>-1. Hence, we can say that Time Complexity of given relation will be equal to O(n^k.logn^(p+1)). Thus, substituting values of k and p, we get time Complexity as O(logn).

2) Let's assume that T(1)=1. We know that T(n)=T(n/2)+n^2/2+n ----(1)

T(n/2)=T(n/4)+(n/2)^2/2+(n/2). Similarly,

T(n/4)=T(n/8)+(n/4)^2/2+(n/4). Let's assume this continues k times (Until (n/2^k) becomes 1).

Therefore, T(n/2^(k-1))=T(n/2^k)+(n/2^(k-1))^2/2+(n/2^(k-1)).

Substituting in equation (1),

T(n)=T(n/2^k)+(n^2)/2(1+n^2/4+n^4/16+...+((1/2^(k-1))^2))+n(1+1/2+1/4...+1/2^(k-1)).

T(n)=1+(n^2)/2.[2.(1-(n/2)^k)/(2-n)]+2n(1-(1/2)^k)

Also, n/2^k=1 => k=log(n) to the base 2. Thus,

T(n)=1+(n^2)/2.[2.(1-(n/2)^logn)/(2-n)]+2n(1-(1/2)^logn).

Thus, Time Complexity is O(n^logn).