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
Varieties of Arrays In some languages, size of an array should be established once and for all at program design time and can't change during execution. Such arrays are known a

The quick sort algorithm exploit design technique Divide and Conquer

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

Q. Explain that how do we implement two stacks in one array A[1..n] in such a way that neither the stack overflows unless the total number of elements in both stacks together is n.

Define neotaxonomy. Discuss how electron microscopy can help in solving a zoological problem faced by taxonomist.

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.

Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?

Q. Take an array A[20, 10] of your own. Suppose 4 words per memory cell and the base address of array A is 100. Find the address of A[11, 5] supposed row major storage.