All Q&A

1

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)+Θ(n ^{2}) **

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.**

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.

4

**Write quick sort algorithm.** **Analyze the best case and worst case time complexities of your algorithm. ****Perform the PARTITION operation once(one time) on the following array as per the requirement of the quicksort algorithm, assuming the last element of the array to be the pivot element. Clearly mention the steps. Arr=[2,8,7,1,3,5,6,4].**

The array A[p….r] is divided into two subarrays A[p…….(q-1)] and A[(q+1)…….r] where q is the partitioning element.

5

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

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.

Subjects

Browse Streams

- Previous 2 of 2
- Next