Can anyone please tell me the time complexities of these following two java codes (a) & (b)

Question

I'm confused with the time complexities of these two codes:

code 1:

I suppose its O(n^3)

void easy(in n, int x, inty) 
{
    for(int i=0; i<n: ++i) { //o(n)
        if(x<y) {
            for(int k=0: k < n*n: ++k) { //o(n^2)
                System.out.println("k =" +k);
            }
        } else {
            System.out.println("i =" +i);
        }
    }
}

code 2:

void find(int n)
{
    for(int i=0; i<20; ++i) {   //o(1)
        for(int j=0: j<n; ++j) {   //o(n)
            for(int k=0; k<j; ++k)   //o(n)
                System.out.println("k =" +k);

            for(int m=0; m<i; ++m) //o(1)
                Systen.out.println("m =" +m);
        }
    }
}

I suppose its o(n^2)

Maybe if you explained how you arrived at these proposed answers, and what about them you do not trust, you might get more useful information. — Scott Hunter, Nov 29 '17 at 19:01
oh ok, I'll do that.. Actually this is the first time I asked a question on this website so wasn't really sure what to write like comments and stuff :( — Ayesha, Nov 29 '17 at 19:05
@Ayesha have a look at the question I referred to, it's a good intro to big O — fvu, Nov 29 '17 at 19:11

score 1 · Accepted Answer · answered Nov 29 '17 at 19:10

In the first snippet you have an outer loop of n iterations. Then the body of that loop either performs n^2 operations (if x<y) or one operation (if x>=y). This means that the running time is either O(n) or O(n^3), depending on the values of x and y.

In the second snippet you have an outer loop with an i variable that doesn't depend on n. It goes from 1 to 20, which means you can count it as constant amount of time, so lets get rid of that loop.

We have the following loops remaining:

for(int j=0: j<n; ++j) {
    for(int k=0; k<j; ++k)
        System.out.println("k =" +k);

    for(int m=0; m<i; ++m)
        Systen.out.println("m =" +m);
}

Now the outer loop has n iterations. The second inner loop depends on i, which is constant, so that entire loop takes constant time.

The first inner loop takes O(n), since k goes from 0 to j, and j goes from 0 to n. Hence the total running time is O(n^2).

Can anyone please tell me the time complexities of these following two java codes (a) & (b)

1 Answers1