4 ms·

100 and 1000 are both slightly less than powers of 2, so 2 has a slight advantage for these numbers. For sufficiently large numbers, 3 always wins. Here is a pr

100 and 1000 are both slightly less than powers of 2, so 2 has a slight advantage for these numbers. For sufficiently large numbers, 3 always wins. Here is a proof: If there are a total of N options, the number of choices is x * d, where d is the smallest integer larger than log_x(N). When N is large enough you can approximate d by log_x(N), so the number of choices is x log N / log x. We are looking for the x that minimizes x / log x (in any base). Let us arbitrarily choose base 2. So 2 / log 2 is 2, whereas 3 / log 3 is only 1.89. Incidentally, to see that the minimum of the continuous function x / log x is reached at e (although this has no relevance to the discrete problem), take the derivative and set it to zero, giving 1 / log(x) - 1 / log^2(x) = 0, or log x = 1, giving x=e (differentiation rules are always in base e.) Finally, if his proposition is right, does it mean that a ternary tree is a more efficient data structure than a binary tree, when there is a natural ternary separation? This whole argument is based on an arbitrary -- and IMO, rather flimsy -- measure of efficiency as the product of depth and width. The optimal branching factor for an n-ary tree depends on many factors and is heavily dependent on the details of the implementation; no single n is always optimal. For example, when traversal of the tree involves disk seeks, a very large n such as 512 or 1024 is used.

madcaptenor 17y ago
For what it's worth, over the range N = [59050, 65536] = [3^10+1, 2^16], the number of choices in a ternary tree is 311 = 33, and in a base-2 tree is 216 = 32; 65536 is the largest N for which binary wins over ternary. They tie a few times for even higher N, for the last time at the interval [3^17 + 1, 2^27] = [129140164, 134217728]; ternary trees with number of leaves in this interval have 18 levels, binary trees have 27. The point is that "sufficiently large" here turns out to be so large that nobody would actually build a phone tree that large, which is true for lots of mathematical results about "sufficiently large" numbers.

madcaptenor 17y ago

For what it's worth, over the range N = [59050, 65536] = [3^10+1, 2^16], the number of choices in a ternary tree is 311 = 33, and in a base-2 tree is 216 = 32; 65536 is the largest N for which binary wins over ternary. They tie a few times for even higher N, for the last time at the interval [3^17 + 1, 2^27] = [129140164, 134217728]; ternary trees with number of leaves in this interval have 18 levels, binary trees have 27. The point is that "sufficiently large" here turns out to be so large that nobody would actually build a phone tree that large, which is true for lots of mathematical results about "sufficiently large" numbers.