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

- Math and Science
- Math Homework Help
- Geometry Assignment Help
- Algebra Assignment Help
- Trigonometry Homework Help
- Statistics Homework Help
- Calculus Homework Help
- Science Homework Help
- Biology Assignment Help
- Chemistry Homework Help
- Social Science Help
- Psychology Assignment Help
- Literature Help
- Do My Homework
- History Assignment Help
- Custom Assignment Help

- Computer Science
- Languages:C/C++/C#,Java, VB, .Net
- Databases: SQL, Oracle, SQL Server
- Mysql Homework Help
- Data structures and algorithm
- Operating Systems Help
- Computer Networks Homework Help
- UML Diagrams Help
- Python Homework Help
- Java Homework Help
- Java Servlets Help
- IT Assignment Help
- English Help
- Law Help
- Coursework Help
- Help With Assignment

- Engineering
- Biotechnology Asisgnment Help
- Chemical Engineering Help
- Civil Engineering Help
- Computer Sc & Engineering
- Electrical Engineering Assignment Help
- Mathematics & Computing
- Mechanical Engineering Assignment Help
- Medical Science Help
- Nursing Assignment Help
- Textile Technology
- Humanities Assignment Help
- Arts & Architecture
- Political Science
- Commercial Cookery

- Business studies
- Perdisco Assignment Help
- Finance Homework Help
- Accounting Homework Help
- Marketing Assignment Help
- Economics Homework Help
- Human Resource Help
- Operations Management Help
- Strategy & planning Help
- Project management Help
- Business development Help
- Case Studies Help
- Research Paper Help
- Essay Writing Help
- Dissertation Writing
- SPSS Homework Help