In Wikipedia, it says

the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size.

However, a random access machine is by definition a register machine, whose registers can store any non-negative number.

In addition, the concept of "word" is even not mentioned in the Wikipedia page of random access machine.

So what's the difference between transdichotomous model and RAM?


1 Answer 1


The transdichotomous model is first proposed by Michael Fredman and Dan Willard [1]. They wrote the motivation as

... On the other hand, with the inclusion of division and Boolean operations, they obtain a linear time algorithm. This linear time algorithm, however, suffers from an abuse of the unit cost assumption. In particular, the algorithm generates operands during the course of its computation whose individual lengths are $N^2$ times the length of the largest of the $N$ numbers to be sorted.

What seems to be needed is a computational model that avoids the potential abuses of the unit cost random access machine, but allows for unit cost operations among operands of “reasonable” size, i.e., operands of size commensurate with the sizes of the numbers to be sorted. Accordingly, we consider a reformulation of the sorting problem wherein our machine has a $b$-bit word size, and each of the $N$ input numbers is assumed to be a non-negative integer less than $2^b$ (and hence each tits into one word). Moreover, it is desirable that a sorting algorithm use only $O(N)$ words of memory.

That is to say, in contrast with RAM model, the transdichotomous model is less powerful because it does not allow unit cost operations on arbitrary large number. For example, in the sorting problem where the largest number is $m$, the transdichotomous model only allows unit cost operations on numbers no more than $m$.

[1] Fredman, M. L., & Willard, D. E. (1993). Surpassing the information theoretic bound with fusion trees. Journal of computer and system sciences, 47(3), 424-436.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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