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
The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

1. Write a pseudocode algorithm to print the numbers from 1 to 10, and then from 10 to 1, using exactly one loop. 2. The function contains() takes a food as an argument and tell

red black tree construction for 4,5,6,7,8,9

In assignment, you have already started the process of designing a database for the Beauty Salon mini-case (enclosed again below), mainly in the phase of conceptual database design

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

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

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame