# Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| < 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.

• Try to follow the proof of Theorem 2.5 applied to your function $\phi(S)$ and see what (if anything) goes wrong. – Yuval Filmus May 4 '14 at 0:44

• What do you mean by "at least $O(n)$"? "At least" gives a lower bound; $O(\cdot)$ gives an upper bound. "At least something smaller than $n$" actually gives no information. – David Richerby Jun 30 '14 at 13:42