CODEWITHSUNDEEP
javaalgorithm
blackhazelnut
blackhazelnut

Reputation: 60

what is the complexity of this code snippet?

I have a question in regards to the time complexity of the below code. I am guessing that the time complexity is, O(n^3) but my friend told me that the time complexity should be O(n^2). However, I am still not convinced with the answer. My stand is that:　the first and second for loop would cost O(1/2 n^2) and inner loop would need another some O(n) complexity. Therefore, it is about O(n^3).

for (int i = 1; i <= len; i++) {
    for (int j = i + 1; j <= len; j++) {
        int mid = (i + j) / 2;
        for (int k = i; k <= j; k++) {
            dist[i][j] += Math.abs(A[k - 1] - A[mid - 1]);
        }
    }
}

Upvotes: 2

Views: 368

Answers (1)

Salvador Dali
Salvador Dali

Reputation: 222551

So you need to find the time complexity of something like this:

for (int i = 1; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) {
        for (int k = i; k <= j; k++) {
            // some O(1) operation
        }
    }
}

Each of the loops run in O(N), so the complexity is O(N^3). You can also write a simple test program in your language (I wrote in python):

def check(N):
    s = 0
    for i in xrange(1, N + 1):
        for j in xrange(i + 1, N + 1):
            for k in xrange(i, j + 1):
                s += 1
    return s

print [check(i) for i in xrange(1, 10)] // [0, 2, 7, 16, 30, 50, 77, 112, 156]

And checked for a closed form for this sequence. It is enter image description here,

which is clearly O(n^3)

Upvotes: 2

Related Questions