Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:ahmadh:ch5 [2018/03/11 08:45] – ahmadh | courses:cs211:winter2018:journals:ahmadh:ch5 [2018/03/13 02:48] (current) – ahmadh | ||
|---|---|---|---|
| Line 109: | Line 109: | ||
| Since our Merge-and-Count procedure takes O(n) time, the rimming time T(n) of the full Sort-and-Count procedure satisfies the recurrence (5.1). Therefore, the Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions, and runs in O(n log n) time for a list with n elements. | Since our Merge-and-Count procedure takes O(n) time, the rimming time T(n) of the full Sort-and-Count procedure satisfies the recurrence (5.1). Therefore, the Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions, and runs in O(n log n) time for a list with n elements. | ||
| + | |||
| + | ==== 5.3.2 Comments ==== | ||
| + | |||
| + | I feel like this was one of the sections where class discussion was very important. Just reading the algorithm alone did not make much sense to mean, and I struggled understanding the key reason why the algorithm returns a sorted list along with the count. It did not seem necessary to me when I was reading this section before--however, | ||
