Time Complexity and BigOH Question 7 (6 points): Consider the following pseudoco

Question

Time Complexity and BigOH

Question 7 (6 points): Consider the following pseudocode Algorithm multisearch( data, target): data an list of arrays of integers; in each array the integers are sorted in ascending order; the list data has a cursor. target: an integer // Iterate over the arrays in the list 'data' using // its cursor data.goFirst) found false while( !data.after) and !found ) 1 // search for integer 'target' in A found -binarySearch (data.currentItem ), target) data.goForth () Using the active operation approach to timing analysis determine the time complexity of this pseu docode in the worst case. Assume that the list of arrays contains n arrays and that each array has exactly m items in it. Show all your work and express your final answer in Big-O notation.

Explanation / Answer

The worst case would be when all the lists are searched using Binary search and still the element is not found.

Hence as we know the complexity of binary search is O(log m) where m is the number of elements in array

and Number of arrays is n so binary search procedure will run n times

hence the time complexity is O(n*(log m))

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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