confusion with worst case for direct addressing
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)$.