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
1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

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

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti

Q. Sort the sequence written below of keys using merge sort. 66, 77, 11, 88, 99, 22, 33, 44, 55                                                                      Ans:

Data Structure and Methods: Build an array structure to accomodate at least 10 elements. Provide routines for the following: An initializer. A routine to populate (

the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

write an algorithm for multiplication of two sparse matrices using Linked Lists

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real