Best case, Data Structure & Algorithms

Assignment Help:

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


Related Discussions:- Best case

Adjacency list representation, Adjacency list representation An Adjacen...

Adjacency list representation An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V,

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Degree of node, Q. The degree of a node is defined as the number of childre...

Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Implement the physat algorithm, The first assignment in this course require...

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Deletion algorithm for dequeue, Deletion Algorithm for dequeue Step 1:...

Deletion Algorithm for dequeue Step 1: [check for underflow]   If front = 0 and rear = 0   Output "underflow" and return Step 2: [delete element at front end]   If front

Multiple queue, algorithm for multiple queue with example program

algorithm for multiple queue with example program

Fifo, give any example of page replacement using fifo and use your own refe...

give any example of page replacement using fifo and use your own reference string

Abstract data type-stack, Conceptually, the stack abstract data type mimics...

Conceptually, the stack abstract data type mimics the information kept into a pile on a desk. Informally, first we consider a material on a desk, where we might keep separate stack

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd