A d-dimensional vector(ui, u2, . . . , uu) screens the vector(v1, v2, . . . , vd

Question

A d-dimensional vector(ui, u2, . . . , uu) screens the vector(v1, v2, . . . , vd iff there is a permutation on {1. 2.. d) such that ul > Vm( 1 ). u2 > t,(2). . . . , ud > Vm(d) . For example. 7.9.4) screens 7.6,3) because one permutation of the latter is 6.7.3). On the other hand, 7.9.4.5) does not screen 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).

Explanation / Answer

Assuming the vectors are arrays we can have the following approach:

We have two vectors u and v. We are checking whether u screens v.

We will sort u and v by any efficient algorithm with log n complexity like quicksort. Now we will compare element by element form both the u and v and we should get
the corresponding elemnets in u will be greater than the corresponding element in v. In simple terms u[i] > v[i].The complexity of this approach will be
log n + log n + n = 2log n + n

2 log n for sorting two vectors and n is for comparing the corresponding elements of u and v. The complexity will be O(n) as for larger n it is more dominating
than log n . It is same for worst or avearge case complexity will be similar to the complexity of sorting.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.