3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The running time of an algorithm can depend on the data structure being used. $\endgroup$ – Yuval Filmus Dec 7 '17 at 14:43
  • $\begingroup$ I agree. That question is so vague that it borders on useless. $\endgroup$ – Raphael Dec 7 '17 at 14:54
1
$\begingroup$

The term "data structure" typically refers to a way to organize/store data, and the operations to create, maintain, and access them.

The asker is probably expecting you to assume specific implementations, probably as given in the course, then come up with algorithms to access the median, and discuss their respective runtime cost.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.