Comparisions and assignments in worst case, Data Structure & Algorithms

Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?       

Ans:

The worst case performance occurs in insertion sort occurs when the elements of the input array are in descending order. In that case, the first pass requires one comparison, the second pass requires two comparisons, third pass three comparisons till the kth pass requires (k-1), and in the end the last pass requires (n-1) comparisons. Therefore,  we obtain the total numbers of comparisons as follows :

f(n)    = 1+2+3+.........+(n-k)+.....+(n-2)+(n-1)

= n(n-1)/2

= O(n2)


 

 

 

Posted Date: 7/10/2012 5:40:43 AM | Location : United States







Related Discussions:- Comparisions and assignments in worst case, Assignment Help, Ask Question on Comparisions and assignments in worst case, Get Answer, Expert's Help, Comparisions and assignments in worst case Discussions

Write discussion on Comparisions and assignments in worst case
Your posts are moderated
Related Questions
Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

To delete an element in the list at the end, we can delete it without any difficult. But, assume if we desire to delete the element at the straining or middle of the list, then, we

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

prove that n/100=omega(n)

Consistent Heuristic Function - Graph Search Recall the notions of consistency and admissibility for an A* search heuristic. a. Consider a graph with four nodes S, A, B, C,

important points on asymptotic notation to remember

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Question 1 Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps. Question 2