Algorithm Analysis Problems #7) Please explain the solution thoroughly it\'s mor

Question

Algorithm Analysis Problems #7)

Please explain the solution thoroughly it's more important than the answer itself. Here is my class work and a provided link to origonal word document. Thank You.

https://docs.google.com/document/d/1sgmQ24EZxDZL7WfqPh_hjz2MNu2wGGvl47rQrmFeagY/edit?usp=sharing

7. (10 pts) Find the average case complexity of the Exchange S algorithm for sorting 3 distinct elements (n-3) for each of the following operations: of assignments of keys and of comparisons. Exchange-Sort (A, n) sorts the Array A(1:n) in non-decreasing order. for 1 to n do for j i 1 to n do exchange (AG), A(i)llt AGO, AG) A(), A(i) t endif end for endfor of camp of assinen

Explanation / Answer

Exchange-Sort(A, n)
   for i=1 to n do // THis for loop runs n time : i = 1 to n
       for j=i+1 to n do // THis foe loop runs (n-1), (n-2), (n-3),...1, 0 for i = 1, 2, ...(n-1), n respectively
           if A(j) < A(i) then // THis takes constant time : O(1)
               exchange(A(j), A(i))
           endif
       endfor
   endfor

   So time complexity:
       (n-1) + (n-2) + (n-2) + ...+1
       = (n)(n-1)/2

       = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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