# confusion with worst case for direct addressing

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?

• 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. – gnasher729 Aug 25 at 22:30
• Does n depend on m? Otherwise O(m-n) would be the same as O(m). – siracusa Aug 26 at 1:58
• 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 – Naveen Aug 26 at 2:19
• @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. – D. Ben Knoble Aug 26 at 5:40
• @D.BenKnoble To be fair, there were no links when I posted my comment. That's why I posted it, to improve the question. – 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)$$.