0
$\begingroup$

Consider a quadratic function over positive integers. For example say a simple function of the form: $f(n)=3n+4n^2$

Now given any positive integer $C$ find two integers such that: $f(i)-f(j) = C$

What is the complexity of such problems? I tried searching for a bit but didn't find an answer..

$\endgroup$
1
  • 1
    $\begingroup$ I encourage you to edit your post to describe the motivation/context and why this will be helpful to others. $\endgroup$
    – D.W.
    Mar 22 at 21:07

1 Answer 1

0
$\begingroup$

Here is one possible approach. With $f(n) = an + bn^2$ we have, $C = (i-j)(a + b(i+j))$. Given any $C$, find a factor of it. Let $C = \alpha\beta$ with $\alpha \le \beta$. Now we have to solve for $i - j = \alpha$ and $a + b(i+j) = \beta$. Given any $C$ we have to only enumerate upto $\sqrt{C}$ to get all integral factorizations. Once we have a factorization we can solve the equations to test where integral solution exists. We iterate from 1 upto $\sqrt{C}$ an in each iteration we do some constant number of division operations which again would be of order at most $\sqrt{C}$. Thus overall complexity is $O(C)$.

$\endgroup$

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.