I'm trying to get through one of the exercises in Okasaki's "Purely Functional Data Structures," where he presents a zeroless binary numbers as a structure for random-access list, and asks to
9.6 Show that
updateon element i now run in O(log i) time.
"now" here contrasts zeroless representation with a plain binary tree backed random access list, for which the lookup and update time was estimated as O(log n).
The approach in both cases similar: we maintain a Cons list of "digits", with every non-zero digit containing a tree of size corresponding to the digit's weight. The list as a whole is a binary (or a zeroless binary) representation of the number of elements in the list.
For example, a list of 6 elements,
[1, 2, 3, 4, 5, 6] (binary for 6 is 111, zeroless binary is 22) will look as
[ Zero, One(Node(Leaf(1), Leaf(2)), One(Node(Node(Leaf(3), Leaf(4)), Node(Leaf(5), Leaf(6)))) ]
in binary, or
[ Two(Leaf(1), Leaf(2)), Two(Node(Leaf(3), Leaf(4)), Node(Leaf(5), Leaf(6)) ]
in zeroless binary representation. Now, the
update times are defined by the time you spend locating the tree with the i-th element, and by the time you spend navigating that tree.
What I don't get is why loookup of i th element in a binary random access list takes O(log n) rather than O(log i)? We need to locate the tree containing the i th element — that's O(log i), navigation within the tree is capped by O(log w), where w is the size of the tree, which is clearly less than i*2.
What do I miss?