How to verify the running time of an algorithm?

Question

I made coded the global alignment algorithm using affine gap cost. The algorithm running time in big-O notation is O(n^2). However, my teacher in the class said that in order to verify the running time one has to divide the running time with n^2 where n is the length of the sequence (using sequences of different lengths). And if (n,R(n)/n^2) is below a horizontal line then the running time is verified. I couldn't really understand what that meant. I plotted R(n)/n^2 using sequences of different lengths. And it worked. I had fluctuations in the beginning but then the fluctuations went away (you can see this in the image too). The sequences I used were from 1000 bases long to 10,000 bases long. Can someone how R(n)/n^2 verifies the running time? I've tried looking on the internet but couldn't find a possible answer. Forgive me, if my question is too simple. I do not have a computer science background.

Answer 1

The running time being O(n^2) means there will always exist 2 real positive numbers b and n0 such that, for every n >= n0,

R(n) <= b*(n^2), where R(n) is the running time function.

In other words, the running time stays lower than a function of the form b*(n^2).

---

If you take that inequality and divide everything by (n^2), you get:

R(n)/(n^2) <= b

and the Big O definition still applies.

So as long as R(n)/(n^2) stays below b for n >= n0, then R(n) is O(n^2). Again, in other words, this means staying below the constant function b (horizontal line).

What you are doing is plotting R(n)/n^2 and checking if the graph stabilizes horizontally, for sufficiently high n.

This is easier than plotting R(n) and trying to identify if the graph is approximately a quadratic function (quadratic functions are quite similar to cubic and higher order polynomials, don't you agree?). If R(n) was actually O(n^3), R(n)/(n^2) would give you a crescent function, and you'd verify that in your graph.

Answer 2

If we say an algorithm is in O(n²), we actually mean the number of steps needed to run the algorithm as a function of input size n is in O(n²).

When we say a function is in O(n²), we actually mean there is a positive constant c so that f(n) < c * n² for big input sizes n.

This is equivalent to saying: there is a positive constant c so that c > f(n) / n² for big input sizes n.

You already noticed that your graph above converges towards a constant value. This is your c.

Of course, the number of steps needed to run an algorithm depend on the machine you use.

Answer 3

Some maths. (Sorry, but you do need a bit of maths to really understand this.)

The notation f(n) is O(n^2) means that:

1) define g(n) = f(n) / n²

2) the limit as N tends to infinity of g(n) is C, where C is some constant

Intuitively, that says the g(n) function gets closer and closer to C as n gets larger and larger. A mathematician would say that it "converges" to C.

(Actually, the maths is a bit more complicated than that, but I'm very rusty. And I'm trying to keep this simple.)

What your graph is doing to demonstrating that g(n) does actually converge. And the C value is that value on your Y-axis that corresponds to the straight line that your graph is approaching ... as the value on the X-axis goes to infinity.

Answer 4

To explain it even simpler: An algorithm in O(n²) is like a quadratic function. You can always divide a quadratic function by a function of the form a * b² to get a constant function.

Answer 5

O(n²) is defined as the set of functions R(n) such that, for some constant c, R(n) ≤ cn² for all sufficiently large n.

That inequality is equivalent to ^R(n)/_n² ≤ c.

So your teacher is suggesting that you plot ^R(n)/_n² to see that, for sufficiently large n, you get (roughly) a constant c.

Note that this plot is not a formal proof. It's just a helpful visualization.