3. Answer the following questions about the MysteryScan algorithm below. Input: data: sorted linked list with...

  

Transcribed Image Text:

3. Answer the following questions about the MysteryScan algorithm below. Input: data: sorted linked list with n integers Input: search: unsorted array with n integers to search for Input: n: size of data and search 1 Algorithm: MysteryScan 2 output = Array (n); 3 node = data.head; 4 for i=1 to n do 5 while node.value > search[i] and node # data.head do | node=node.prev; end 10 11 12 while node.value <searchli] and node # data.tail do | node=node.next; end if node.value = search[i] then output[i] = node; output [i] = nil; else 13 14 15 16 end 17 return out; end a. What is the maximum number of times that the while loop in lines 5-7 can iterate during one iteration of the outer for loop? Justify your answer. Answer the following questions about the MysteryScan algorithm below. Solution: b. What is the maximum number of times that the while loop in lines 8-10 can iterate in one iteration of the outer loop? Solution: c. Find the worst-case time complexity of MysteryScan. Show your work. Solution: 3. Answer the following questions about the MysteryScan algorithm below. Input: data: sorted linked list with n integers Input: search: unsorted array with n integers to search for Input: n: size of data and search 1 Algorithm: MysteryScan 2 output = Array (n); 3 node = data.head; 4 for i=1 to n do 5 while node.value > search[i] and node # data.head do | node=node.prev; end 10 11 12 while node.value <searchli] and node # data.tail do | node=node.next; end if node.value = search[i] then output[i] = node; output [i] = nil; else 13 14 15 16 end 17 return out; end a. What is the maximum number of times that the while loop in lines 5-7 can iterate during one iteration of the outer for loop? Justify your answer. Answer the following questions about the MysteryScan algorithm below. Solution: b. What is the maximum number of times that the while loop in lines 8-10 can iterate in one iteration of the outer loop? Solution: c. Find the worst-case time complexity of MysteryScan. Show your work. Solution:

Answer rating: 100% (QA)

Lets go through the MysteryScan algorithm step by step What does the MysteryScan algorithm do The MysteryScan algorithm searches for elements in an un... View the full answer