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 to9.6 Show that lookup and update on 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 lookup and 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?
Time complexity of update and lookup in binary random access list
data structures;functional programming;complexity