Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

can someone explain me the difference between those two (cell probe model and transdichotomous ram)?

In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of memory reads/writes. Can I use words as pointers in that model? Is the memory size fixed or unbounded?

In transdichotomous ram memory is a table of words indexed from 0 to S - 1 for given S. words have fixed size and serve as pointers. I can read/write constant number of cells at constant time. What about complexity of operations? Are computation free?

I don't feel the difference between them.

Thanks for help!

share|cite|improve this question
The main practical difference is that the simpler cell probe model is used for lower bounds, while the more complex transdichotomous RAM model is used for upper bounds. – Jeff╬Á Nov 5 '12 at 17:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.