img
All Q&A
2

Why Recursion tree method is best than the Substitution method for solving a recurrence relation?  Find the asymptotic upper bound of the following recurrence relation with the help of recursion tree method.

T(n)=T(n/4)+T(n/2)+Θ(n2)

29 March, 2024
Recursion tree method is best than the Substitution method for solving a recurrence relation because in recursion tree method, we draw a recurrence tree and calculate the time taken by every level of tree.
3

What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication. 

29 March, 2024
It is a problem solving technique like divide and conquer where problems are divided into subproblems. Dynamic programming is used when the subproblems are not independent.
5

Find the recurrence relation of binary search and derive the time complexity of binary search.

29 March, 2024
Binary search is a technique to find a particular element in a sorted list of elements. Suppose L is the sorted list and d is the element to be searched, lb is the lower bound of the list and ub is the upper bound of the list.