The median of a set of numbers is the \"middle\" number. For example, the median

Question

The median of a set of numbers is the "middle" number.
For example, the median of [6,4,1,8,12] is 6 because there are 3 numbers in the set bigger than or equal to 6 and 3 numbers in the set smaller than or equal to 6. This means 6 is in the middle.
As another example, the median of [6,4,1,12] is 5, because there are 2 numbers in the set bigger than or equal to 5 and 2 numbers in the set smaller than or equal to 5. This means 5 is in the middle.
Here is an algorithm to find the median of a sorted array of numbers.

MedianOfSorted(array A)
// Store length of A
n = length(A)

// If n is odd, then the median is one of the numbers in A
if n%2 == 1 then
// if n is odd, then the median is at the position in
// A given by the ceiling of n/2
return A[ceiling(n/2)]
else
// otherwise it is the average of the numbers at position
// n/2 and the one after that
return ( A[n/2] + A[n/2 + 1] ) / 2
end MedianOfSorted

What is the time efficiency of this algorithm in Big-Oh notation? Justify your answer.

Explanation / Answer

Time effieciency of this algorithm in Big-Oh notation is O(1)

that is constant as it is just checkinig whether length of array is odd or even and just accessing element form array which is constant operation and doing one simple arithematic operation and returning result.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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