CODEWITHSUNDEEP
algorithmbig-ocode-analysis
Saiyan
Saiyan

Reputation: 197

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

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?

Upvotes: 1

Views: 1121

Answers (2)

nevets
nevets

Reputation: 4828

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.

Upvotes: 1

JosEduSol
JosEduSol

Reputation: 5456

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

Upvotes: 0

Related Questions