?i N Home | My Sac State Attendance Quiz (425/ × | P ) ?, Cole Radio-Now Pla | 4

Question

?i N Home | My Sac State Attendance Quiz (425/ × | P ) ?, Cole Radio-Now Pla | 4. My Drive-Google Drive + v ?https://csus.instructure.com/courses/27775/assignments/263589#submit Attendance Quiz (4/25/I8). Due 4/ZITIO IISY PIMM Home Due Friday by 11:59pm Points 10 Available until Apr 27 at 11:59pm Submitting a file upload File Types pdf Assignments Discussions Grades People Files Syllabus Collaborations Blackboard Col Hello CSC 20 Students, Given the following algorithm: To sort an array A[O. N-1]: for (int last-N-1; last»-1; last--)( // Move the largest entry in A[O.. last] to Alast] for (int index 0; index- last-1; index) I Dashboard Courses Calendar //swap adjacent elements if necessary Inbox if (Alindex]Alindex 1]) [ Smarthinking Online Tutoring Office 365 Follett Discover int temp Alindex]; A[index]-A[index+1]; Alindex1] temp; Help 1. Compute the TOTAL primitive operations 2. Compute the Big O for the algorithm K- 8:03 PM Type here to search 4/25/2018 13

Explanation / Answer

Hi,

GIven program is nothing but Bubble Sort.

Case 1) O(n) (Best case) This time complexity can occur if the array is already sorted, and that means that no swap occurred and only 1 iteration of n elements

Case 2) O(n^2) (Worst case) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs. Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

So totla number of primitive operation: n(n+1)/2

Time: O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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