(a) Given an unsorted array A[1...n] of distinct integers numbers and is given a

Question

(a) Given an unsorted array A[1...n] of distinct integers numbers and is given a nonnegative integer number, k, k < n. You need to find an element from A such that its rank is k, i.e., there are exactly (k-1) numbers less than or equal to that element. Example: Input: A = [1, -3, 4, 3, 12, 20, 30, 7, 14, -1, 0] and k =8. Output: 12, since 7, -3, -1, 0, 4, 3, 1 (8-1=7 numbers) are all less than or equal to 12 Suggest a sub-quadratic running time complexity algorithm (only pseudo code) to solve this problem. Justify.

(b) Given an array A of n + m elements. It is know that the first n elements in A are sorted and the last m elements in A are unsorted. Suggest an algorithm (only pseudo code) to sort A in O(mlogm +n) worst case running time complexity. Justify.

(c) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant): T(n) = 3T(n/3) + 2cn; T(1) = 0 What is the running time complexity of this algorithm? Justify.

(d) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place.

(d.1) What is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search?

(d.2) What is the worst-case complexity of your improved insertion sort if only swaps/inversions of the data values are taken into account?

Explanation / Answer

a)

We have Sub-quadratic time time complexity so use bubble sort to sort elements

Step 1:Sort array with buuble sort

Step 2:Return element k-1 from array

c) T(n) = 3T(n/3) + 2cn

Here a=b=3 f(n)=O(n) i.e.c=1

Hence logba=c

Hence a/c to master theoremT(n)=O(nlogba logk+1n) here k=0

O(nlog11log0+1n)

=O(nlogn)

d)

d.1 Binary insertion sort when improved with a binary search to determine the correct location to insert new elements, and therefore performs log2(n) comparisons in the worst case, which is O(n log n)

d.2

The algorithm as a whole still has a running worst case running time of O(n2) because of the series of swaps required for each insertion

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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