Java Data Structure and Algorithm b) The processing time of an algorithm is desc

Question

Java Data Structure and Algorithm

b) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant): T(n) = 3T(n/3) + 2cn; T(1) = 0 What is the running time complexity of this algorithm? Justify. c) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. c.1) What is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search? Justify. c.2) What is the worst-case complexity of your improved insertion sort if only swaps/inversions of the data values are taken into account? Justify.

Explanation / Answer

b) T(n) = 3T(n/3) + 2cn; T(1) = 0

By Term Expression,

T(n) = 3(3T(n/3^2) + 2cn/3) + 2cn

= 3^2T(n/3^2) + 4cn

= 3^2(3T(n/3^3) + 2cn/3^2) + 4cn

= 3^3T(n/3^3) + 6cn

........

= 3^iT(n/3^i) + 2icn

Set i = log n base 3; Use T(1) = 0

We get,

T(n) = 0 + 2(log n)cn = O(n log n)

c) The algorithm for insertion sort by using binary search can be look like below:

INSERTION-SORT(A)

for j = 2 to length[A]

do key = A[j]

     i = j - 1

while i > 0 and A[i] > key

    A[i+1] = A[i]

    i = i - 1

A[i+1] = key

c.1) Let T(n) denote the worst-case time for the comparisons in binary search

Recurrence is T(n) = T(n) + O(1)

Worst case time complexity is T(n) = O(n)

c.2) Let T(n) denotes the worst-case time for swapping in binary search

Worst case time complexity is T(n) = O(1)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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