Suppose that you want to find the largest element in an unsorted array of n elem

Question

Suppose that you want to find the largest element in an unsorted array of n elements. Algorithm A searches the entire array sequentially and keeps track of the largest element seen thus far. Algorithm B sorts the array using mergesort, and then reports the last element as the largest. 1. What is the big-O time efficiency of Algorithm A in the best, average, and worst cases? Explain your answer briefly. (You do not need to implement either algorithm. We just want you to analyze them.) 2. What is the big-O time efficiency of Algorithm B in the best, average, and worst cases? Explain your answer briefly. 3. Which algorithm is faster? Explain briefly.

Explanation / Answer

1) time complexity for sequential search is:

if item present in array:

Best Case Worst Case Average Case

O(1) O(n) O(n/2)

if item is not present:

Best Case Worst Case Average Case

O(n) O(n) O(n)

2)

for merge sort complexity for every case is O(n log n) and for selecting last element of array is O(1). so for big data it is very expensive.

merge sort complexity

Worst-case performance O(n log n)

Best-case performance O(n log n)

Average performance O(n log n)

3) for my point of view sequential search is good approach compare to merge sort:

expalination:

if n=1000 then sequential search will take 1000 time

and for merge sort will take 1000*log(1000)=3000 times

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---