How would I articulate the time complexity of an O(n^3) function?

Question

For a pseudocode algorithm like this:

Algorithm fn(A, S):
    Inputs: array A of n integers
            integer S

    for i from 0 up to n - 1:
        for j from i + 1 up to n - 1:
            for k from j + 1 up to n - 1:
                if A[i] + A[j] + A[k] == S:
                    return true

    return false

Why is its worst-case time-complexity O(n^3). I am new to big-O notation and I need a bit of help explaining why this function's worst-case would be O(n^3). I reasoned that it was O(n^3) because it has three for loops; but, I also feel that this is a shallow understanding.

Answer 1

What you have shown is an example of a polynomial-time algorithm. You’re correct that the worst case would be O(n^3) from the THREE nested for loops.

The worst case in this example would be if a match between the values of A[i] + A[j] + A[k] and the intger S was not found until the very last possible nested iteration. Contrastingly, the best case would be if the match were found on the first time through.

Answer 2

It is rather simple, really. Nested for loops yeld a number of iteration that is the product of the number of iterations of every single loop.

This makes sense, because you have to repeat the inner loop for every iteration of the outer loop. So for I 1..10 for J 1..10 will loop 10 times on J for every one of the 10 iterations on I. Ten times every ten times is a typical product application. Imagine a square where for every 10 rows you have 10 cells.

So, in a worst case scenario, where none of the loops ends prematurely, if the three loops went from 0 to n-1 the length (iterations) of each one would be n.

Thus the three nested loops would take n * n * n operations or n^3 in said worst case scenario (if they started at zero).

Usually as all this matters only for big numbers, you only look at the bigger term: O(n^2+n+3) is really O(n^3), and as you are trying to divide problems in solvable and not solvable you consider O(2n) and O(n) the same, or at least on the same scale. You repeat n times "something" (that can be 1,2,3 steps but you repeat it n times).

Now, in this case, the loops starts from the previous loop variable, so how many iterations would they do? Imagine a square n*n divided in cells. In each row take only the cells that have a horizontal position (j) greater than the vertical position (i). What you get is a triangle that has roughly half the cells of the square, so every inner loop is roughly O(1/2 n).

In this case, if you count the iterations, they are n * 1/2 n * 1/2 n and you repeat that times the contents of the inner loop (that is a fixed number of computer operations, does not depend on n), you can ignore the real inner number of operations and you can also ignore the 1/4 and so O(n^3) it is.