Analysis of running time of code fragment using Big-Oh notation

Question

sum = 0; 'O(1)
for(i=1;i<2*n;i++) 'O(2n-1)
    for(j=1;j<i*i;j++) 'O((2n-1)^2 - 1)
        for(k=1;k<j;k++) 'O((2n-1)^2 - 1 - 1)
            if (j % i == 1) 'O(1)
                sum++;

When I add and simplify everything, I get O(n^2). The solution says O(n^4). What mistake have I done?

possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — David Eisenstat, Sep 01 '14 at 22:14
Then I should do O(1) * O(2n-1) * O((2n-1)^2 - 1) * O((2n-1)^2 - 1 - 1) * O(1) but it does not give O(n^4). Are the values for each line correct? — Saiyan, Sep 01 '14 at 22:52
It gives you O(n^5) which *is* correct, because big-O is an upper bound. To get a tight bound, you need to work out the sums, which is a math question. — David Eisenstat, Sep 01 '14 at 22:54

nevets · Answer 1 · 2014-09-02T18:50:30.160

For nested loops, you should apply multiplication rule instead of addition rule; for separate tasks, you should apply addition rule.

You can think the problem in this way: you are given N task, and each of the task has a complexity of O(M), what will be the complexity in total? We have 2 ways to interpret this, one uses addition rule, and the other uses multiplication rule.

Let's see addition rule first. To get the answer, we need to add up the complexity of all these N task since they are all independent, which is N * O(M), which is equivalent to O(N) * O(M) = O(NM).

Another interpretation will be: iterating through all the tasks requires O(N), each of the task requires O(M), thus O(N) * O(M) = O(NM).

Bear in your mind that the big O notation notates the upper bound of a complexity, since your O(N^5) is more loose than O(N^4), so it's conceptually correct, but is not entertained. Why we will encounter this situation? It's because the third loop has been loosened too much. The actual complexity of the third loop is O(j), and the upper bound for j is (2n-1)^2 - 2. However, if you just take the O((2n-1)^2 - 2) as the complexity of the third loop and multiply it as we did before, it's interpreted as every loop of K has a complexity of (2n-1)^2 - 2, which is not true.

score 0 · Answer 2 · answered Sep 02 '14 at 18:14

As a complement to other answers, a more analytic/mathy (and hard) approach is to compute:

enter image description here

You can compute this in Mathematica (or in WolframAlpha online) as:

Sum[Sum[Sum[1, {k, 1, j - 1}], {j, 1, i^2-1}], {i, 1, 2*n-1}]

The result is a polynomial of degree 5.

Also this can be useful sometimes to check your results.

It could be done by hand using finite calculus, (you can see Knuth's book for this topic).

Analysis of running time of code fragment using Big-Oh notation

2 Answers2