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!

  • 4
    $\begingroup$ 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. $\endgroup$ – Jeffε Nov 5 '12 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.