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
Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

/* 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

This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.

Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

1. Start 2. Get h 3. If h T=288.15+(h*-0.0065) 4. else if h T=216.65 5. else if h T=216.65+(h*0.001) 6. else if h T=228.65+(h*0.0028) 7. else if h T=270.65 8.

The data structure needed for Breadth First Traversal on a graph is Queue

Objectives The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. Background An arbitrary BST i

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion