Four Problems Involving Complexity of Algorithms and Sorting

See Questions.pdf

• Questions.pdf

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

3.a.
In the worst case, the two elements that are out-of-order occur at the last comparison (between the last and the (n-1)th item of the list).
In this case are performed n-1 successive comparisons before the algorithm to return either TRUE (if the list is already sorted) or FALSE (if the last two elements are out-of-order).

For the provided list, it is clear that last element must be < the (n-1)th element and the rest of 3 elements must be in order.
The arrangements that yield the worst-case are (in each case are performed 5-1=4 comparisons):
1,2,3,5,4 (5,4 is out of order)
1,2,4,5,3 (5,3 is out of order)
1,3,4,5,2 (5,4 is out of order)
2,3,4,5,1 (5,1 is out of order)
If we try to move the item 5 to the left, then the out of order pair will be discovered after 3 comparisons only and the worst case is not yielded anymore....