Question: A d-dimensional vector h(u1, u2, . . . , ud)screens the vector h(v1, v2, . . . , vd) iff there is a permutation on
A d-dimensional vector h(u1, u2, . . . , ud)screens the vector h(v1, v2, . . . , vd) iff there is a permutation on {1, 2, . . . , d} such that u1 > v(1), u2 > v(2), . . . , ud > v(d) . For example, h(7, 9, 4) screens h(7, 6, 3) because one permutation of the latter is h(6, 7, 3). On the other hand, h(7, 9, 4, 5) does not screen h(7, 6, 3, 5). The last example also shows that we can have vectors u and v, neither of which screens the other. Using pseudo-code, give an algorithm which determines, given two vectors u and v, whether u screens v. It should return True iff u screens v. If it helps, you an assume that vectors are arrays. Make the algorithm as efficient as you can, and state, as precisely as you can, its worst-case time complexity (and, if possible, average-case as well).
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
