The worst-case happens if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. Therefore, we must compare each element A[j] along with each element in the entire sorted subarray A[1 .. j − 1] and so tj = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j − 1) tests. Consequently, tj = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:

And using the summations, we have

This running time can be expressed as (an2 + bn + c) for constants a, b and c that again depends on the statement costs ci. Therefore, T(n) is a quadratic function of n.

Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order

PLACE ORDER NOW

- 24 x 7 Availability.
- Trained and Certified Experts.
- Deadline Guaranteed.
- Plagiarism Free.
- Privacy Guaranteed.
- Free download.
- Online help for all project.
- Need Assignment Help

Read More

## Follow Us