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.