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
What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

How do you find the complexity of an algorithm?  Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that

/* The program accepts matrix like input & prints the 3-tuple representation of it*/ #include void main() { int a[5][5],rows,columns,i,j; printf("enter the order of

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Write a program to create a hashed file that stores the records currently in the file " data_2013 ". Records should use the same fixed-length schema given previously, and should ag


For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr