Consider an interconnection-network SIMD computer with n processors where each processor has a fixed-size local memory and is connected to each of the other n-I processors by a two-way link. At any...

Consider an interconnection-network SIMD computer with n processors where each processor has a fixed-size local memory and is connected to each of the other n-I processors by a two-way link. At any given step a processor can perform any amount of computations locally but can communicate at most one input to at most one other processor. A sequence S is stored in this computer one element per processor. It is required to search S for an element x initially known to one of the processors. Show that Q2(log n) steps are required to perform the search.