Talk:Computational complexity of mathematical operations

From Wikipedia, the free encyclopedia

I suppose that where you say:

"Here, complexity refers to the time complexity of performing computations on a Turing machine."

you should say:

"Here, complexity refers to the time complexity of performing computations to a RAM (Random Access Machine)."

Usually when talking about polynomical time operations, RAM models are used instead of TM. This is because we can simulate a RAM in a TM, but only with an overhead of n^2. They are equally powerfull but minimum time, changes.

Thanks for pointing this out. Fredrik Johansson 19:52, 31 March 2007 (UTC)