CODEWITHSUNDEEP
time-complexitybig-o
Bobbalob
Bobbalob

Reputation: 27

Did i calculate the Big O for these functions correctly?

I tried to find the time complexity of the following two functions: the first one

public static int myMethod1(int[] arr) {
    int x = 0;
    for (int i = 0; i < arr.length / 2; i++) {
        for (int j = 0; j < arr.length; j++) {
            for (int k = 0; k < arr.length; k++) {
                x++;
                if (k == arr.length / 2) {
                    break;
                }
            }
        }
    }
    return x;
}

So with this one i am thinking. The method contains 3 loops, and the loops are iterating over variable i, j and k… i and j, and k are both incremented by 1 for each passing… this gives us as N For each LOOP which leaves us with three N’s.., which gives is O(N^3)

The next one is:

public static int myMethod(int N) {
    int x = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N / 2; j++) {
            for (int k = 1; k < N;) {
                x++;
                k *= 2;
            }
        }
    }
    return x;
}

With this i am thinking. The method contains 3 loops, and the loops are iterating over variable i, j and k… i and j are both incremented by 1 for each passing… this gives us as N For each LOOP which leaves us with two N’s.. The last loop k doubles, which gives is log(n). The result of the this problem is therefore O(N^2· log (N))

is this correct? and if it is not, why?

Upvotes: 2

Views: 74

Answers (1)

e.ad
e.ad

Reputation: 380

You are right. In both of the questions

Upvotes: 1

Related Questions