Suppose we are given a list of real numbers, and we want to know whether the lis

Question

Suppose we are given a list of real numbers, and we want to know whether the list contains any duplicate elements. The following two algorithms solve this problem, returning true if some pair of list elements are the same, and false if not. Find the worst-case running time of each algorithm using Theta notation. Justify your answer by referring to the pseudocode. Which algorithm is more efficient in the worst case? Find the best-case running time of each algorithm using Theta notation. Justify your answer by referring to the pseudocode. Which algorithm is more efficient in the best case?

Explanation / Answer

(a) Worst Case:
   Worst case is when last and second last element is same.Then for each outer loop iteration i,inner loop will iterate i-1 times.
   MatchRxistsA() :
   i.e outer loop: 2 , 3 ,4 ,5...
       inner loop: 1 , 2 ,3, 4...
   Therefore complexty will be: n(n-1)=theta(n^2)

   MatchExistsB() :
   In worst case (i.e array is sorted in decending order),Insertion sort's time complexity is theta(n^2)
   for "for" loop complexity is theta(n)
   Therefore overall complexty is: theta(n^2)

   Hence worst time complexity of both algorithm is same.

(b) Best Case:
   Best case is first and second elements are same.
   MatchRxistsA() :
   In this case outer loop and inner will execute one time each .Therefore complexity is theta(1) i.e constant time.

   MatchExistsB() :
   Best case time complexty of insertion sort is O(n)
   And for loop will execute 1 time.
   Therefore overall time complexty will be theta(n).

   Hence in best case Algorithm "MatchRxistsA()" is more efficient than MatchExistsB().

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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