CODEWITHSUNDEEP
algorithmtime-complexity
Harminder
Harminder

Reputation: 2229

Complexity of algorithm

What is the complexity given for the following problem is O(n). Shouldn't it be O(n^2)? That is because the outer loop is O(n) and inner is also O(n), therefore n*n = O(n^2)?

The answer sheet of this question states that the answer is O(n). How is that possible?

public static void q1d(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
}

The complexity for the following problem is O(n^2), how can you obtain that? Can someone please elaborate? 

public static void q1E(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n/2; j++) {
            count++;
        }
    }
}

Thanks

Upvotes: 6

Views: 367

Answers (5)

Shashwat
Shashwat

Reputation: 2668

Both are O(n^2). Your answer is wrong. Or you may have written the question incorrectly.

Upvotes: 0

debracey
debracey

Reputation: 6607

Your answer sheet is wrong, the first algorithm is clearly O(n^2).

Big-Oh notation is "worst case" so when calculating the Big-Oh value, we generally ignore multiplications / divisions by constants.

That being said, your second example is also O(n^2) in the worst case because, although the inner loop is "only" 1/2 n, the n is the clear bounding factor. In practice the second algorithm will be less than O(n^2) operations -- but Big-Oh is intended to be a "worst case" (ie. maximal bounding) measurement, so the exact number of operations is ignored in favor of focusing on how the algorithm behaves as n approaches infinity.

Upvotes: 0

parapura rajkumar
parapura rajkumar

Reputation: 24423

The complexity of both code is O(n*n)

FIRST

The outer loop runs n times and the inner loop varies from 0 to n-1 times

so

total = 1 + 2 + 3 + 4 ... + n

which if you add the arithmetic progression is n * ( n + 1 ) / 2 is O(n*n)

SECOND

The outer loop runs n times and the inner loop varies from 0 to n-1/2 times

so

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

which if you add the arithmetic progression is n * ( n + 1 ) / 4 is also O(n*n)

Upvotes: 6

Yuushi
Yuushi

Reputation: 26080

The first example is O(n^2), so it seems they've made a mistake. To calculate (informally) the second example, we can do n * (n/2) = (n^2)/2 = O(n^2). If this doesn't make sense, you need to go and brush up what the meaning of something being O(n^k) is.

Upvotes: 15

zerkms
zerkms

Reputation: 255115

First case is definitely O(n^2)

The second is O(n^2) as well because you omit constants when calculate big O

Upvotes: 2

Related Questions