a) Write the pseudocode for an efficient algorithm that computes the 25th and 75

Question

a) Write the pseudocode for an efficient algorithm that computes the 25th and 75th percentile (i.e, returns the identity of the (N/4)th and (3N/4)th elements) in an array of unsorted of integers. Assume that you already habe a method PARTITION(A,p,r) which partitions A[p,.....,r] around the element at A[r] and returns the position of this element in A after partition.
b) What is the average complexity of the algorithm you provided? Why?

(25 pts) Q4a) (10pts) Write the pseudocode for an efficient algorithm that computes the 25th and 75h percentile (i.e. returns the identity of the (N/4)th and (3N/4)h elements) in an array of unsorted of integers. Assume that you already have a method PARTITION(A.p.r) which partitions A(p, r] around the element at A[r] and returns the position of this element in A after partition. 04b) (5pts) What is the average complexity of the algorithm you provided? Why?

Explanation / Answer

func find_number_at(A, p, r, i) //finds number at index i in sorted Array A

{

index = partition(A, p,r )

if index == i

then return A[i]

else if index < i

then return find_number_at(A, index, r, i-index)

else

return find_number_at(A, p, index, i)

}

find_required_numbers(A)

{

find_number_at(A, 1, n, n/4)

find_number_at(A, 1, n, 3n/4)

}

Time complexity

---------------------------

Imagining the partiion function takes O(n) complexity, on an average case the partion function splits the array into 2 halfs and we continue searching in only one half so the running time will be O(n+n/2+n/4.....) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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