Complexity of algorithm

Question

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

I think upper one is O(n^2).and what doubt you have about second one? — WordsWorth
– WordsWorth, Commented Jan 17, 2012 at 5:27
This means the answer provided by my professor is incorrect hmm. — Harminder
– Harminder, Commented Jan 17, 2012 at 5:29

Jason Down · Accepted Answer · 2012-01-17 05:32:09Z

15

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.

edited Jan 17, 2012 at 5:32

Jason Down

22.3k13 gold badges89 silver badges118 bronze badges

answered Jan 17, 2012 at 5:29

Yuushi

26.3k7 gold badges66 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

parapura rajkumar · Accepted Answer · 2012-01-17 05:33:36Z

6

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)

edited Jan 17, 2012 at 5:33

answered Jan 17, 2012 at 5:28

parapura rajkumar

24.5k2 gold badges58 silver badges86 bronze badges

2 Comments

Harminder Over a year ago

So if n/2 does it still equal to o(n)? But the iteration for inner loop is half the outer loop does that make any difference?

zerkms Over a year ago

@user1085135: O(n) has the meaning linear. It doesn't matter what constant it multiplied by, what only matters is that it is linear

zerkms · Accepted Answer · 2012-01-17 05:31:20Z

2

First case is definitely O(n^2)

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

answered Jan 17, 2012 at 5:31

zerkms

256k73 gold badges447 silver badges551 bronze badges

Comments

debracey · Accepted Answer · 2012-01-18 05:34:32Z

0

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.

edited Jan 18, 2012 at 5:34

answered Jan 17, 2012 at 5:33

debracey

6,6372 gold badges32 silver badges58 bronze badges

5 Comments

David Schwartz Over a year ago

The second algorithm won't be less than O(n^2), it is precisely O(n^2). I suspect you aren't quite clear on what "O(n^2)" actually means. It means that as n approaches infinity, the run time increases for the algorithm for two values of n is proportional to the difference between those n values squared.

debracey Over a year ago

No. In practice, the actual time complexity of the algorithm will be slightly less than O(n^2). However, because Big-Oh is a maximal bound, we say it is O(n^2). You are correct that the n/2 factor is clearly bounded by n -- as I indicated in my answer. There are other bounding measurements (ie. Big-Theta) that compute the bounding factor differently.

David Schwartz Over a year ago

Why do you think the actual time complexity of the algorithm will be less than O(n^2)? I claim it will be precisely O(n^2) because the algorithm's complexity precisely matches the definition of O(n^2). If it's not exactly O(n^2), then nothing is. We say it is O(n^2) because it is O(n^2). You seem to want to make this fuzzy, confusing, and imprecise when it is absolutely, crystal clear.

debracey Over a year ago

Because the actual complexity is O(n^2) + C, where C is some constant. In this case C is negative. So it will be slightly less than straight n^2. The C is insignificant, but you still should write the "answer" as O(n^2) - C

David Schwartz Over a year ago

A complexity of O(n^2) + C means precisely the same thing as a complexity of O(n^2).

Shashwat · Accepted Answer · 2012-07-17 06:53:55Z

0

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

answered Jul 17, 2012 at 6:53

Shashwat

2,6888 gold badges44 silver badges58 bronze badges

Collectives™ on Stack Overflow

Complexity of algorithm

5 Answers 5

Comments

2 Comments

Comments

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

2 Comments

Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related