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
need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

i need help in java recursion assignment.

Question 1 Write a program in 'C' to read N numbers and print them in descending order Question 2 Discuss the properties of ADT Question 3 Write a note on

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.

Illustrate the Back Face Detection Method A single polyhedron is a convex solid, which has no external angle between faces less  than 180° and there is a simple object space me

A Binary Search Tree is binary tree which is either empty or a node having a key value, left child & right child. By analyzing the above definition, we notice that BST comes int

Explain State Space Tree If it is convenient to execute backtracking by constructing a tree of choices being made, the tree is known as a state space tree. Its root indicates a