# Worst time complexity for finding a median number for a list and array data structure

This was a question that came up in a past exam paper in my computer science course, it states:

"There are two simple, un-optimised sorted data structures, each storing n numbers. The first is a list; the second is an array. What is the worst-case complexity of extracting the median number from each data structure? Are the averages cases different? Why?"

I would like to know the answer to this question as I am confused on what is being asked? Should we not be analyzing algorithms like binary search and not the data structures themselves?

• The running time of an algorithm can depend on the data structure being used. Commented Dec 7, 2017 at 14:43
• I agree. That question is so vague that it borders on useless. Commented Dec 7, 2017 at 14:54

If your data structure is sorted, you don't need to use binary search to find the median — you just need to access the correct element. Accessing an arbitrary element in an array takes time $O(1)$, but in a list it could take $\Theta(n)$. This shows that the running time of an algorithm could depend on the data structure, since the running time of operations on the data structure figures in the time complexity of the algorithm.