Why is the Big-O complexity of this algorithm O (n ^ 2)?

Question

I know that the big complexity of this algorithm is O(n^2) , but I cannot understand why.

 int sum = 0; int i = 1; j = n * n; while (i++ < j--) sum++; 

Even if we set j = n * n at the beginning, we increase i and decrease j at each iteration, so there shouldn't be a resulting number of iterations much less than n*n ?

Answer 1

At each iteration, you increase i and decrement j , which is equivalent to simply increasing i by 2. Therefore, the total number of iterations is n ^ 2/2, and this is still O (n ^ 2).

Answer 2

big-O complexity ignores odds. For example: O(n) , O(2n) and O(1000n) are all the same O(n) . Similarly, O(n^2) and O(0.5n^2) are O(n^2) times.

In your situation, you essentially increase the loop counter by 2 each time through your loop (since j-- has the same effect as i++ ). Thus, your run time is O(0.5n^2) , but the same as O(n^2) when removing the coefficient.

Answer 3

You will have exactly n*n/2 loop iterations (or (n*n-1)/2 if n is odd). In the large O record, we have O((n*n-1)/2) = O(n*n/2) = O(n*n) , because the constant factors are not taken into account.

Answer 4

Your algorithm is equivalent

 while (i += 2 < n*n) ... 

which is equal to O(n^2/2) , which is the same as O(n^2) , because the great complexity of O does not care about constants.

Answer 5

Let m be the number of received iterations. Then,

i + m = n ^ 2 - m

what gives,

m = (n ^ 2-i) / 2

In the Big-O record, this means O (n ^ 2) complexity.

Answer 6

Yes, this algorithm is O (n ^ 2).

To calculate the complexity, we have a table of complexity:

O (1) O (log n) On) O (n log n)
O (N²) O (n ^ a) O (a ^ n) O (n!)

Each line is a set of algorithms. The set of algorithms that is in O (1) is also in O (n) and O (n ^ 2), etc. But not in reverse order. So your algorithm implements n * n / 2 sentences.

O (n) O (nlogn) O (n * n / 2) O (N²)

So the set of algorithms that include the complexity of your algorithm is O (n²), since O (n) and O (nlogn) are smaller.

For example: For n = 100, the sum = 5000. => 100 O (n) 200o (n * logn) 5000 (n * n / 2) 10000 (n ^ 2)

Sorry for my english.

Answer 7

Despite the fact that we start j = n * n at the beginning, we increase i and decrease j at each iteration, so there should not be a resulting number of iterations much less than n * n?

Yes! That is why O (n ^ 2). By the same logic, it is much smaller than n * n * n , which makes it O (n ^ 3). This is even O (6 ^ n), by a similar logic.

big-o gives you upper bound information.

I believe that you are trying to ask why the complexity is theta (n) or omega (n), but if you are just trying to understand what big-O is, you really need to understand that it gives upper bounds for functions in the first place .