Consider the obvious algorithm for chocking whether a list of integers is sorted

Question

Consider the obvious algorithm for chocking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is out of order. In that case, return false. If no such pair is found by the time we reach the end of the list, return true. Our elementary operation is a comparison between two integers. (a) What is the worst case running time of this algorithm on an input list containing n elements? Write all 5-element input lists which contain the numbers 1, 2, 3, 4, 5 and yield the worst case. (b) What is the best case running time of this algorithm on an input list with n elements? How many input lists are there which have size n, all elements being different, and yield the best case? (c) Suppose that the input list is a random permutation of 1, 2, ..., n and all such permutations are equally likely. Derive the average-case expected running time. Give both an exact and asymptotic answer.

Explanation / Answer

Part a. The worst case aymptotic running time of the algorithm would O(n). This would be the case if the list completely sorted. In this case as 1 2 3 4 5. Here it would start comparing pairs so (1,2), (2,3), (3,4), (4,5). Since here none of the elements violate the property the algorithm would keep checking to the end of the list and at the end return true.

Part b. The best case running time for the algorithm would be O(1). This would be case when the first element is bigger than the second element irrespective of what the rest of the list might look like. In n elements the number of input list would be n-1 + n-2 + n-3 ..... +1. This would be so because if the first element is the highest in the list then there are n-1 choices for second element. If it is the second highest then there are n-2 choices and so on. At the end if the element is the second lowest then the only choice is the lowest.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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