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
Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

Example: Assume the following of code: x = 4y + 3 z = z + 1 p = 1 As we have been seen, x, y, z and p are all scalar variables & the running time is constant irrespective

Merging 4 sorted files having 50, 10, 25 and 15 records will take time


Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

Determine the greatest common divisor (GCD) of two integers, m & n. The algorithm for GCD might be defined as follows: While m is greater than zero: If n is greater than m, s

Q. Explain the various memory allocation strategies.                                                            Ans. M e m ory Allocation Strategies are given as follow

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


The searching technique that takes O (1) time to find a data is    Hashing is used to find a data