Comparisions and assignments in worst case, Data Structure & Algorithms

Assignment Help:

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)


 

 

 


Related Discussions:- Comparisions and assignments in worst case

Construct a minimum spanning tree, Construct G for α, n, and W given as com...

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Darw a flowchart that inputs country someone is visiting, Regis lives in Br...

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

Binary search, Explain binary search with an example

Explain binary search with an example

Nested for loop, nested for loop for (i = 0; i for (j = 0; j seq...

nested for loop for (i = 0; i for (j = 0; j sequence of statements } } Here, we observe that, the outer loop executes n times. Every time the outer loop execute

Applications of the queue, Write down any four applications of the queues. ...

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Stack, Explain the array and linked list implementation of stack

Explain the array and linked list implementation of stack

Generic doubly linked list, Your objective is to write a generic doubly lin...

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

Postfix expression, Ask question Write an algorithm for the evaluation of a...

Ask question Write an algorithm for the evaluation of a postfix expression using a stack#Minimum 100 words accepted#

Postfix expression algorithm, Write an algorithm to calculate a postfix exp...

Write an algorithm to calculate a postfix expression.  Execute your algorithm using the given postfix expression as your input : a b + c d +*f ↑ . T o evaluate a postfix expr

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd