Problem 10 : Write and solve the recurrence equations for the time complexity of

Question

Problem 10 : Write and solve the recurrence equations for the time complexity of the following recursive algorithms. Explain why your equations are correct.

1. To search for a value in a sorted list, compare it to the middle value, and search the right half of the list if it is larger, and the left half if it is smaller.

2. The maximum of a list of numbers is the larger of the maximum of the first half and the maximum of the second half.

3. To sort a list of numbers, divide the list into four equal parts. Sort each part. Merge these sorted four lists into two sorted lists, and then merge the two into one.

Explanation / Answer

1.) Since it divides the list in two halves therefore recurrence relation will be:

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

From master theorem, a = 1, b = 2 , k = 0 and p =0

Since a=bk and p>=-1. We will have

T(n) = O(nlogba* log p+1n) = O(n0log n) = O(log n)

2.) This theorem divides the algo in two parts and each part is evaluated. So recurrence relation will be

T(n) = 2T(n/2) + c.
From master theorem, we have a = 2, b = 2 and k = 0 and p =0

Since a > bk. Therefore,

T(n) = O(nlogba) = O(nlog22) = O(n).

3.) As mentioned, list is divided into four equal parts, then merged into two lists and then merge into one. So we will have

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

From Master theorem, a=4, b=4, k = 1 and p=0

Since, a=bk and p>=-1. We will have

T(n) = O(nlogba* log p+1n) = O(nlog44 * log n) = O(nlog n)

Hope it helps, feel free to comment in case of any query.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.