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
1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

Write a program for reversing the Linked list

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

In this part, students are allowed to implement the following simplifications in their table and data design. o Availability for the beauty therapists don't have to be considere

Asktypes of pipelining question #Minimum 100 words accepted#

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

Question 1 Write the different characteristics of an algorithm Question 2 Explain in brief the asymptotic notations Question 3 Write an algorithm of insertion sort and e