6. (7 points)Exercise 2.3-4 (pp. 39). You need to first provide the recursive al

Question

6. (7 points)Exercise 2.3-4 (pp. 39). You need to first provide the recursive algorithm (parts of it given below; complete it), using pseudocode conventions, and then develop and state the two recurrence relations. You do not have to provide the constant values; instead use O(1) for a constant value, (n) for a constant multiplier of n, etc. You do not need to solve the recurrences. Insertion-sort-recursive(A[1..n]) if n>1 then key= i- while is0 and Alij-key T(n)- ifn=1;t(n) = T(- )+ if n> 1

Explanation / Answer

if n > 1 then

insertion-sort-recursive(A[1..n-1])

key = A[n]

i = n - 1

while i > 0 and A[i] > key

A[i+1] = A[j]

i = i - 1

A[i+1] = key

**T(n) = O(1) if n = 1 ; T(n1)+ O(n) if n > 1

**Comment for any further queries. Upvote if the answer is satisfactory.

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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