# What is the Computational Complexity of this Difference of Squares problem?

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..

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

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