Exercise 40: Mathematical analysis of the Adjacent Pair Permutation method

Summary

The APP algorithm processes each each pair permutation. Each pair permutation forms a search tree. Perform an analysis on the number of nodes in a typical pair permutation tree given that:

There are W words

There are E entity types per word

The fraction of pair permutations that transform is Q

Solution

I wasn't quite sure how to solve this one, so I called on Mr. Vaughn Climenhaga for some help, and he delivered! Thanks Vaughn!

The following solution assumes that only the first two pair permutations are considered, which is a best-case scenario. (I'm unclear on whether the algorithm is feasible with this limitation)

So basically O(E^2W * Q^W).

In the case where W = 15, E = 10, and Q = 0.1, we have:

344,926,315,789,473,684,201 = 344,926 * 316 trillion

In the case where W = 15, E = 10, and Q = 0.01, we have:

6,553,401

In the case where W = 15, E = 10, and Q = 1/150, we have:

44,175

In the case where W = 7, E = 10, and Q = 0.01, we have:

25,401

In the case where W = 7, E = 10, and Q = 1/150, we have:

3,892

Discussion

In practice, the algorithm's search tree appears to be much, much smaller than this, so perhaps Q can't be modeled as a constant.

The other important consideration is that Unique APP avoids branching to fragments it has already searched, which heavily prunes the tree.