In CLRS there is an exercise for direct address table

Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of S. What is the worst-case performance of your procedure?

for this question i have seen a lot of websites indicating the worst case possibility is O(m) by starting and examining every non null slot up to end and then returning the maximum index, but i think it can be done in a faster way than that. If direct addressing tables has m slots , then obviously the highest value should be in the end (i thought keys are treated as indexes in direct addressing,correct me if i am wrong) , so if we start iterating from the end then worst case would be O(m-n) where n is the number of elements examined by our iterator before reaching non null value from end of the direct addressing table

is something wrong with my approach? Can any one clear this topic?

  • $\begingroup$ You are using terms that seem to be specific to your course. I have no idea what CLRS means, what you mean by "dynamic set" (is that a mutable set? ), and what you mean by "direct-address table". Either explain these terms, or you will have to wait for an answer for a long time. $\endgroup$ – gnasher729 Aug 25 at 22:30
  • $\begingroup$ Does n depend on m? Otherwise O(m-n) would be the same as O(m). $\endgroup$ – siracusa Aug 26 at 1:58
  • $\begingroup$ yes n depends on m, i have a assumption why it could be O(m) but i dont know whether it is correct, if we start iterating from end and the element is present in the top of the list and all other slots are null then it could be O(m) @siracusa $\endgroup$ – Naveen Aug 26 at 2:19
  • $\begingroup$ @gnasher729 to be fair, CLRS is the rather-standard abbreviation for the linked textbook, and the terms are well-specified in the context of that textbook. $\endgroup$ – D. Ben Knoble Aug 26 at 5:40
  • 1
    $\begingroup$ @D.BenKnoble To be fair, there were no links when I posted my comment. That's why I posted it, to improve the question. $\endgroup$ – gnasher729 Aug 26 at 15:58

When iterating from start to end, you always need to examine $m$ items, which is $O(m)$.
When iterating from end to start, in the worst case you need to examine $m - |S|$ items, then the answer depends on the relationship between $|S|$ and $m$.

If $m - |S|$ is const., it takes $O(1)$ time.
Otherwise since $0 \leq |S| \leq m$, we have $m - |S| \leq m$, the upper bound is also $O(m)$.

Then in either cases, as long as $m - |S|$ is not const., both approaches have $O(m)$.


A "direct-address table" maps a subset of keys from 0 to m-1 to values. It would be nonsense if the values were equal to the indices - in that case instead of a "direct-address table" we would just use a bitmap.

So while "dynamic set is represented by a direct-address table" is not defined, I assume the set elements are the values stored in the table. So to find the largest, you need to visit all the entries used for elements of the set, and since we don't know which entries correspond to set elements without checking that they are null, we need to visit all m elements of the direct-address table.


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.