2

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 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?

  • Could you please edit your question to provide more detail on how the data structure works? I am having a difficult time visualizing it. – user22815 Sep 11 '15 at 16:15
  • Added code examples; can add a proper description, but that'll render the question almost unreadable I'm afraid – alf Sep 11 '15 at 16:23
  • 5
    I was actually thinking a description. Code is okay, but that is a bit much. How does the list differ from other types of lists? How does it use the tree? In plain English. – user22815 Sep 11 '15 at 16:26
  • Well, as I was planning the better wording of the question, I came up with an answer; will it make sense to edit the question still — and answer it immediately — or is it better to just remove it? – alf Sep 11 '15 at 21:16
  • 1
    I recommend updating the question and self-answering. I would be interested to hear about this different data structure. – user22815 Sep 11 '15 at 21:23
1

Well, compliments to @snowman for the advice to rewrite the question in plain English — I came up with an answer while doing that.

The O(log n) boundary comes from the way binary numbers work: they have zeroes. For instance, a binary for 8 is 100, or, reversed, 001. So the binary random access list of 8 elements (e.g. [1, 2, 3, 4, 5, 6, 7, 8]) will have the following structure:

[
  Zero,
  Zero,
  One(
    Node(
      Node(
        Node(Leaf(1), Leaf(2)),
        Node(Leaf(3), Leaf(4))
      ),
      Node(
        Node(Leaf(5), Leaf(6)),
        Node(Leaf(7), Leaf(8))
      )
    )
  )
]

Here, it's clear that any element will take exactly 2 log n steps to get to (if you don't trust me on this one, play with n = 2^k, e.g. 256, 1024, 65536...). So the premise that "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" was basically all wrong: the size of the tree does not depend on the element's index, and the position of the tree is dictated by the bits of n, not i.

In zeroless numbers, on contrary, we always have at least one tree of each possible size, so we can be sure that the tree will indeed be located in O(log i), and its size will be not more than 2i.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.