We are using Sequential Search to search an array of size n. It is known that th

Question

We are using Sequential Search to search an array of size n. It is known that the item we are looking for is definitely present in the array. The probability that the item we are looking for is the last one in the array is 1/3, and the probability that the item we are looking for is the next to last one is also 1/3. The probabilities of matching the search key to each of the other items are all equal. If n = 15, counting a comparison as the basic operation, what are the values of the complexity functions for the best case, worst case, and average case? B(15) = _ W(15) = _ A(15) = _ We found that under these conditions when n = 20, the running time for the worst case was 100 n sec (10^-9 sec.). What are the expected running times for the best case, worst case, and average case when n = 15? Best case: t = Worst case: t = Average case: t =

Explanation / Answer

Answer :

In sequential search, time complexity is as below :
Best case : 1
Worst Case : n
Average case : n/2
So here in our case we have 15 elements so that n=15.
So , best case B(15) : 1
Worst case W(15): 15
Average case A(15): 15/2 = 7.5

In Best case, we just find match of our element with very first element so that it would be 1.
In Worst case, our element is at end of the list so we have to go through all the list so that it would be 15.
In average case, our element is in the middle of the list so our complexity is 15/2 = 7.5.

Now for the running time, we have given running time for the n=20 in worst case is 100 nsec.
Worst case :
So we can calculate the ruuning time for n=15 case,
Like, traversing whole list 20 elements it took = 100 nsec so traversing 15 elements it will take = (15*100 nsec)/20 = 75 nsec
Worst case : t = 75 nsec

Best Case :
traversing whole list 20 elements it took = 100 nsec so traversing 1 elements it will take
= (1*100 nsec)/20 = 5 nsec
Best Case : t = 5 nsec

Average Case :
traversing whole list 20 elements it took = 100 nsec so traversing 15/2 elements it will take = (15*100 nsec)/20*2 = 37.5 nsec
Average Case : t = 37.5 nsec

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.