Solve the following recurrence relations. Do not use the master method. Show all of your work

Question

Recurrence Relation practice solve the following recurrence relations. Do not use the master method. Show all of your work.

1. 1. T(n)=2T(n-1)+c2ⁿ
   2. T(n)=7T(n/2)+c2ⁿ
   3. T(n)=2T(n/2)+n²
   4. T(n)=5T(n/4)+n^1/2

Summary

The solution of the following recurrence relations is:

1. 1.  O(n2ⁿ)
   2.  O(n³)
   3.  O(n²)
   4.  O(n)

 

Explanation

1). T(n)=2T(n-1)+c2ⁿ

Using recursion function

Total cost=2ⁿ+2ⁿ+2ⁿ+2ⁿ………………..+2ⁿ

                          ⁼2ⁿ*n terms

T(n)=2T(n-1)+c2ⁿ= O(n. 2ⁿ)

2). T(n)=7T(n/2)+c2ⁿ

Total cost=n^2*(8/4)^logn2<=n²*2^logn2

= n²*n

= O(n³)

3). T(n)=2T(n/2)+n²

  

Total cost=n²(2-2/T)

= 2 n²-2n

= O(n³)

4). T(n)=5T(n/4)+n^1/2

Total cost= n^1/2 ((2)^logn4+1-1)

= n^1/2(4^logn1/2-1)

= n^1/2(4n^1/2-1)

= 4n- n^1/2

= O(n)

 

Also, read the Given below-defined UML class diagram.