proof of complexity (let all values be ):
is an ancestor of iff is the lowest among all values in the range . This is with probability . Summing this over all for a fixed means the expected number of ancestors is just , which is
proof of complexity (let all values be ):
is an ancestor of iff is the lowest among all values in the range . This is with probability . Summing this over all for a fixed means the expected number of ancestors is just , which is