CSE 374: Algorithms I Worksheet 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 374: Algorithms I
Worksheet 3
[Full Marks 50]
Note: Worksheet problems are more like practice problems to hone your skills through better understanding the concepts. They are easier than homework problems. Solution to every problem should preferably be typed (or, very legibly written in hand on letter size pages). Plagiarism in any form will be strictly dealt with following departmental policy. You should try to solve by yourself as much as possible. You can take help of study materials and book resources and office hours.
Using the recursion tree method, solve the following recurrences. Take as many pages as you want. Clearly show every steps including calculation of tree height, etc. Explain the steps wherever necessary. [10*5 = 50]
1. |
T(n) = T(n/4) + T(n/2) + n2 |
|
2. |
T(n) = 3T(n/4) + n2 |
|
3. |
T(n) = 4T(n/2) + n |
|
4. |
T(n) = 8T(n/2) + n2 |
|
5. |
T(n) = 2T(n/2) + n |
|
6. |
T(n) = 4T(n/2) + n2 |
|
7. |
T(n) = 7T(n/3)+n2 |
|
8. |
T(n) = 7T(n/2) + n2 |
|
9. |
T(n) = T(n/3) + T(2n/3) + n |
|
10. |
T(n) = 2T(n-1)+1 |
|
2023-01-10