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. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.

Triangular Matrices Tiangular Matrices is of 2 types: a)  Lower triangular b)  Upper triangular

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Do you have a library solution for this problem?

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

First - Fit Method: -    The free list is traversed sequentially to search the 1st free block whose size is larger than or equal to the amount requested. Once the block is found it