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
#questionalgorithm for implementing multiple\e queues in a single dimensional array

Maximum numbers of nodes a binary tree of depth d The maximum numbers of nodes a binary tree of depth d can have is 2 d+1 -1.

How to create an General Tree and how to search general tree?

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

Given the following search tree, state the order in which the nodes will be searched for breadth first, depth first, hill climbing and best first search, until a solution is reache

State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

You are supposed to do the following: Write a parallel implementation of the raytracer using pthreads. Measure and compare the execution times for (i) the sequential ver

Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link