CODEWITHSUNDEEP
javaanalytics
THOMASLANG
THOMASLANG

Reputation: 31

Calculating the Big-O of a method

I'm struggling to figure out the O(g(n)) of this algorithm

int a = 1;
for (int i = 0; i< n*n; i++) {
    for (int j = 0; j <= i; j++) {
        if (a <= j) {
            a = i;
        }
    }
}

Upvotes: 3

Views: 87

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

When you have a loop nest like this, it's often helpful to work from the inside out. Notice, for example, that the innermost loop runs Θ(i) times. So, in a sense, the question boils down to determining the work done by this loop:

for (int i = 0; i < n * n; i++) {
    do Theta(i) units of work
}

The work done here is proportional to

0 + 1 + 2 + ... + n2 - 1

We can simplify this by using Gauss's sum:

0 + 1 + 2 + ... + n2 - 1 = n2(n2 - 1) / 2

This final expression is Θ(n4) because it's the product of two quadratic terms. So, overall, the work done is Θ(n4).

Upvotes: 3

Ibrahim Ali Khan
Ibrahim Ali Khan

Reputation: 92

int a = 1;
for (int i = 0; i< n*n; i++) { //Complexity n*n
    for (int j = 0; j <= i; j++) { //Complexty n*n 
        if (a <= j) {
            a = i;
        }
    }
}

O(n) = (n*n) * (n*n) = n^4 roughly

Upvotes: 0

Related Questions