Best case, Data Structure & Algorithms

Best Case: If the list is sorted already then A[i] <= key at line 4. Thus, rest of the lines in the inner loop will not execute. Then,

T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear.

Worst Case: This case arises while the list is sorted in reverse order.  Thus, for execution of line 1, the Boolean condition at line 4 will be true.

So, step line 4 is executed

T (n) = c1n + c2(n -1) + c3(n -1) + c4 (n(n+1)/2 - 1) + c5(n(n -1)/2)  + c6(n(n-1)/2) + c7 (n -1)

= O (n2).

Average case: In mostly cases, the list will be into some random order. That is, it neither sorted in descending or ascending order and the time complexity will lie somewhere among the best & the worst case.

T (n) best       <  T(n) Avg. < T(n) worst

Posted Date: 4/4/2013 6:07:42 AM | Location : United States







Related Discussions:- Best case, Assignment Help, Ask Question on Best case, Get Answer, Expert's Help, Best case Discussions

Write discussion on Best case
Your posts are moderated
Related Questions
: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

how to write a code for for a company , for calculate the salary pay

WHAT IS THE PURPOSE OF STACK IN C

The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

explain collision resloving techniques in hasing


Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca