(Superlinear speedup) Consider the search tree shown in the figure below, in which the dark node represents the solution.
(a) If a sequential search of the tree is performed using a standard depth-first search (DFS) algorithm (going left-to-right), then how much time does it take to find the solution if traversing each arc of the tree takes one unit of time? (Use the tree on the left with one
processor.)
(b) Assume that the tree is partitioned between two processing elements that are assigned to do the search job as shown in the figure on the right. If both processing elements perform a DFS on their respective halves of the tree, then how much time does it take for the solution to be found? What is the speedup? Is there truly superlinear speedup,or is this an anomaly? (If so, then how can you explain it?)