# Is repeated function evaluation constant-time if the function is defined by the entry?

In an algorithm, given a natural number $$n$$, i have to calculate all integer entries of a function $$f_n:R_n\to\mathbb{R}$$ within an interval $$R_n=[a,b]$$ in the real line. Clearly, this amounts to computing $$f_n(x)$$ for every integer $$x\in R_n$$. Both $$f_n$$ and $$R_n$$ depend on $$n$$, this is, they are defined by the input, and yes, they "grow" with its size, since $$f_n$$ is defined as: $$f_n(x)=\sqrt{\frac{x^2}{4}-n}$$ My question is, under what assumptions can I safely say that each evaluation $$f_n(x_0)$$, $$x_0\in R_n$$ is constant in time complexity in terms of $$n$$? This is:

$$\mathrm{Eval}(x,f_n)=\rho(n)=O(1)$$

• What is an "entry"? What is the "region of a function"? What does it mean to say that $f_n$ "grows" with $n$? Do you mean that the running time of $f_n$ increases as $n$ increases? Please edit your post to clarify what you are asking.
– D.W.
Commented May 25 at 23:08
• Thank you for your edit. However, I still have the same questions. The post mentions "calculate all integer entries", but I don't know what an "entry" is. I don't know what "defined by the entry" means. I don't understand what you mean by "they "grow" with its size", or how that is relevant.
– D.W.
Commented May 27 at 20:15

In the RAM model, you can compute $$x^2/4-n$$ in $$O(1)$$ time. It requires only three operations: square $$x$$, divide by $$4$$, subtract $$n$$. The running time to compute $$\sqrt{x^2/4-n}$$ depends on the instruction set. If it includes a sqrt instruction that runs in $$O(1)$$ time, then you can compute $$\sqrt{x^2/4-n}$$ in $$O(1)$$ time. If it doesn't, then it will take longer. The RAM model makes some unrealistic assumptions, such as that you can add or multiply two enormous integers in $$O(1)$$ time, no matter how big they are.
Alternatively, if we care about the bit complexity, then you can compute $$\sqrt{x^2/4-n}$$ in $$O(b^2)$$ bit operations, assuming $$x$$ and $$n$$ are at most $$b$$ bits long. In fact, even lower complexity is possible with fancy algorithms, but those fancy algorithms are only useful in practice once $$b$$ becomes quite large. The bit complexity is a reasonable measure of the size of a hardware circuit needed.