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
A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Write the algorithm for Binary search. Also apply this algorithm on the following data. 22, 44, 11, 88, 33, 55, 77, 66

Surrounding of sub division method A polygon surrounds a viewport if it completely encloses or covers the viewport. This happens if none of its sides cuts any edge of the viewp

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

Illumination of wire frame The colour or shade that a surface appears to the human eye depends primarily on three  factors : Colour and strength of incoming illumination

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for