Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite

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|improve this question
2  
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. – JɛffE Nov 5 '12 at 17:50

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.