The following algorithm checks if the array A is sorted in the ascending order.
n <- A.length
i <- 2
while i <= n
if A[i - 1] >A[i]
i <- i + 1
a) Give its best-case and worst-case running time. Justify your answer.
b) Using a suitable loop invariant, prove the correctness of the algorithm.
c) Write an algorithm to check if a linked list is sorted in the ascending order.
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.
a) First of all, we notice that the algorithm can output “true” (sorted in ascending order) if and only if it is traversed the entire array. On the other hand, it can output “false” at any iteration of the “while” loop.
So the best case is achieved when the algorithm outputs “false” after a comparison (e.g. if a>a) or after a constant number of comparisons (by constant we consider a number c much less than input size n); in this case the algorithm requires O(1) (constant) effort...
This is only a preview of the solution. Please use the purchase button to see the entire solution