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
Draw the process flow diagram: Anand   Dairy (AD) sources 150,000 litres of milk daily from large number of local villagers .The milk is collected from 4:00 AM to 6:00 am and

What is a Binary Search Tree (BST)? A binary search tree B is a binary tree every node of which satisfies the three conditions: 1.  The value of the left-subtree of 'x' is le

AVL trees and the nodes it contains must meet strict balance requirements to maintain O(log n) search time. These balance restrictions are kept maintained via various rotation func

A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

What is quick sort?   Answer Quick sort is one of the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are divided or portio

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

Speed cameras read the time a vehicle passes a point (A) on road and then reads time it passes a second point (B) on the same road (points A and B are 100 metres apart). Speed of t

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t