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 full binary tree with 2n+1 nodes have n non-leaf nodes

need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed


Read the scenario (Pickerings Properties). (a) List the functions of the system, as perceived by an external user. (b) List the external entities. Note that because we are mo

Suppose that there is a Beta(2,2) prior distribution on the probability theta that a coin will yield a "head" when spun in a specified manner. The coin is independently spun 10 tim

When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

Implementing abstract data types A course in data structures and algorithms is hence a course in implementing abstract data types. It may seem that we are paying a lot of atten

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

How does operations like insertion, deletion occur?