Consider the following variant of the EREW SM SIMD model. In one step, a processor can perform an arbitrary number of computations locally or transfer an arbitrary number of data (to or from the...

Consider the following variant of the EREW SM SIMD model. In one step, a processor can perform an arbitrary number of computations locally or transfer an arbitrary number of data (to or from the shared memory). Regardless of the amount of processing (computations or data transfers) done, one step is assumed to take a constant number of time units. Note, however, that a processor is allowed to gain access to a unique memory location during each step (as customary for the EREW model). Let n processors be available on this model to search a sorted sequence S = {s,, s2,.. I s,,} of length n for a given value x. Suppose that any subsequence of S can be encoded to fit in one memory location. Show that under these conditions the search can be performed in O(logt 2n) time. [Hint: Imagine that the data structure used to store the sequence in shared memory is a binary tree, as shown in Fig. 5.10(a) for n = 31. This tree can be encoded as shown in Fig. 5.10(b).]