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?

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

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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