How do I know if a graph is quadratic?

Question

I am a programming student and I am analysing an algorithm efficiency, this algorithm efficiency is so bad that we are expecting it to have a quadratic graph.

After many hours programming and outing everything in the correct place, I got my final graph, but without a function I can't really know if it's quadratic or not.

How can I know ? And does it look quadratic to you math experts ? Here is the image:

Answer 1

This graph is NOT quadratic. To prove, let us assume it to be quadratic.:

Since the graph passes through origin, and it's derivative seems to be $0$ there, it must be of the form $\dfrac{y}{10^7}=ax^2$.

Since the graph passes through the point : $(\approx 3000,10^7)$ Plugging it to equation

$$1=a \cdot (3000)^2 \implies a \approx \frac{1}{3000^2}$$

Now check at $x=9000$, , first from our equation :

$$\frac{y}{10^7}=\frac{1}{3000^2} \cdot (9000)^2 \implies y \approx 27 \times 10^7$$

But in the graph provided, at $x=9000$, $y \approx 8 \times 10^7$.

Answer 2

What you do is plot a few points, you could go into more detail then this if you like with your computer. Then you check to see if the growth is quadratic.

If it is linear then the change between two points is going to be constant.

If it is quadratic then the change between two points will have linear growth.

Your graph looks like it's a bit more then linear, maybe $n\log n$ growth. I don't know of a way to check for that though.

Answer 3

Without a function, nobody can tell if the algorithm's running time is quadratic. You can only say how the running times behave for the range of "set sizes" that are shown in the graph.

It is possible that there is a quadratic or cubic term that is very small for sets up to 10,000 elements but becomes the dominating term for sets larger than 1,000,000 elements.

On the other hand, without knowing what your algorithm is, we cannot even say for sure that the running times are unbounded; maybe your algorithm declares itself "finished" as soon as it reaches $2\times 10^7$ operations, so the running time never gets longer than that.

---

Rather than staring at the graph, you would do better to study your textbook or notes to find the forms of the equations to use to express the asymptotic running times of programs. Then take a careful look at your algorithm and see if there are any ways you can "count" the numbers of operations. The "count" does not have to be exact; if you can say something happens "not more than $x$ times," for example, that is usually something you can use.

Answer 4

You could use regression analysis, such as non-linear least squares (you can google that term). This has the benefit of giving a measure of how well your data fits a quadratic (or some other, perhaps $n \cdot \log(n)$ as suggested in another answer) model.

However, as David K suggested, an analytical approach gets you out of having to pick a model, dealing with "noise" in your data, and the uncertainty of whether the model is useful for cases not covered by your data set. Plus, analysis gives you information that may be useful for optimizing your program, if the need should arise.