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

Develop a material requirements plan, The below figure illustrates the BOM ...

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Implement an open hash table, In a chained hash table, each table entry is ...

In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list.

Method to add an element in circular queue, Q. Let us consider a queue is h...

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

Pest control program, PART- Pest Control Program Prepare a Pest Contro...

PART- Pest Control Program Prepare a Pest Control Program for the facility that will address the management of Rodents, Insects and Birds. Your Pest Control Program should

Graph terminologies, Graph terminologies : Adjacent vertices: Two vert...

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Time required to delete a node x from a doubly linked list, The time needed...

The time needed to delete a node x from a doubly linked list having n nodes is O (1)

Naïve recursive algorithm for binomial coefficients, How many recursive cal...

How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

Memory mapping, lower triangular matrix and upper triangular matrix

lower triangular matrix and upper triangular matrix

Header linked list, creation,insertion,deletion of header linked list using...

creation,insertion,deletion of header linked list using c.

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