0
$\begingroup$

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)$$

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented May 25 at 23:08
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented May 27 at 20:15

1 Answer 1

1
$\begingroup$

It depends on what mathematical model you use for modelling running time.

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.

In the Word RAM model, the running time is the same as the bit complexity (it is lower by a significant constant factor, but that is irrelevant to the asymptotic running time). The Word RAM model is arguably a better model of actual computers. If all numbers are small, the RAM model and Word RAM model end up being equivalent, up to a constant factor.

$\endgroup$
1
  • $\begingroup$ Thanks! I'll use the RAM model, since most integers i'm using will not be that big. $\endgroup$ Commented May 28 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.