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

Explain how two dimensional arrays are represented in memory, Explain how t...

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

Abstract data type- queue, A significant aspect of Abstract Data Types is t...

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Explain the different types of traversal on binary tree, Question 1 What i...

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

Depth first search, DEPTH FIRST SEARCH (DFS) The approach adopted into ...

DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

Data communication, #question.explain different types of errors in data tra...

#question.explain different types of errors in data transmission.

Selection sort, how to reduce the number of passes in selection sort

how to reduce the number of passes in selection sort

State z-buffer algorithm, Z-Buffer Algorithm Also known as the Depth-Bu...

Z-Buffer Algorithm Also known as the Depth-Buffer algorithm, this image-space method simply selects for  display the polygon or portion of a polygon that is nearest to the view

Deletion from a red-black tree, Deletion in a RBT uses two main processes, ...

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

Applications of the queue, Write down any four applications of the queues. ...

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

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