Time complexity of finding predecessor for a dictionary implemented as a sorted array

Question

I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it takes O(1) time.

If the data structure looks something like

[(k0, x), (k1, x), ...]

where the keys k0 to kn are sorted, given k, I thought the successor(D, k) would first have to search the sorted array for k ( $ O(log n) $ ) and then get the successor ( $ O(1) $ ) since the array is sorted, and hence the overall time complexity should be $ O(log n) $ instead of $ O(1) $ as mentioned in the book. This should also apply for predecessor(D, k).

For an unsorted array, the time complexity for predecessor and successor remain as $ O(n) $ since searching the unsorted array also takes $ O(n) $.

Did I misunderstand something?

Answer 1

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key.

But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a sorted random access datastructure.

This particular interface is, in general, more useful and more efficient than the key-based interface previously presented, since it more accurately represents the cost of iterating through the dictionaries elements. Most such interfaces do, in fact, take some kind of cursor ("iterator" in C++ parlance) as an argument and return another cursor as a result.

Answer 2

Usually dictionaries are not sorted. There are no provisions for accessing items in sorted order, and finding the predecessor and successor of a key take O (n) and are not really useful.

What you do however is iterating through a dictionary, that is you have a loop that will visit each key, or each value, or each key-value pair in the dictionary exactly once. Such an iterator would keep track of a position of an item in the dictionary and would have to be able to find the previous or next position in a way that allows visiting each item exactly once, and that is preferably fast.

If you implement a dictionary as a sorted array, going to the previous or next position is trivially O(1), and it just happens to return the items in sorted order. A dictionary implemented as an unsorted array, with n/2 instead of log n access on average to find an existing item, can also trivially iterate in O(1) (and for small n it will be faster because n/2 is still not large compared to log n, and the code is faster).

If you implement a dictionary using a sorted tree, or a hash table, then iterating may be more difficult; but a sorted tree could be stored in an array, and a hash table will often use an array that is not very much bigger than n, so you would expect at least amortized O(1) to iterate (or O(n) to iterate through all elements).