Consider an array A[1..n] such that n = k 2f for some positive parameter k and...

Transcribed Image Text:

Consider an array A[1..n] such that n = k· 2f for some positive parameter k and a positive integer parameter f. We assume that all elements in A have different values. a) Describe an algorithm that runs in time O(n. 2f) and distributes the elements of A among 2f arrays B₁ [1..k]. Any element in the sub-array B; must be smaller than any element in the sub-array B, if i < j. In other words: every element of A is copied to some Bi[j] so that B₁₁[₁] < B₁₂ [2] if and only if i < i2. For example, let A {1,8, 3, 5, 2, 9} and f = 1. Then the array B₁ would contain elements 1, 3, and 2 (in any order) and the array B₂ will contain elements 9, 8, and 5 (in any order). b) Describe an algorithm that achieves the same result as in (a) in time O(n • f). Remark: Observe that f can be very small. For instance, f = log log n. Hence, sorting of the array A would take too much time. Solutions based on sorting the array A (or assuming that the array is sorted) are wrong. - Consider an array A[1..n] such that n = k· 2f for some positive parameter k and a positive integer parameter f. We assume that all elements in A have different values. a) Describe an algorithm that runs in time O(n. 2f) and distributes the elements of A among 2f arrays B₁ [1..k]. Any element in the sub-array B; must be smaller than any element in the sub-array B, if i < j. In other words: every element of A is copied to some Bi[j] so that B₁₁[₁] < B₁₂ [2] if and only if i < i2. For example, let A {1,8, 3, 5, 2, 9} and f = 1. Then the array B₁ would contain elements 1, 3, and 2 (in any order) and the array B₂ will contain elements 9, 8, and 5 (in any order). b) Describe an algorithm that achieves the same result as in (a) in time O(n • f). Remark: Observe that f can be very small. For instance, f = log log n. Hence, sorting of the array A would take too much time. Solutions based on sorting the array A (or assuming that the array is sorted) are wrong. -

Answer rating: 100% (QA)

Lets tackle both parts of your question a Algorithm for On 2f To d... View the full answer