Menu
void bar(int N){
int c=0;
for (int i=0; i<N*N; i++)
for (int j= i; j< N; j++)
c++;
}
The outer (and inner) loops above never get past N. Would this mean the Big O is N*N (N for the outer and N/2 for the inner)?
589
Hence O(n(n+1)/2) = O(n^2). Show activity on this post. AFAIL, being begun from inner loop through outer ones is adequate way for calculation of nested loop complexity.
The loop may, at first glance, look like O(n^2) but the inner loop maximally creates 5 iterations for every iteration of the outer loop. So we receive only 5 * n iterations in total, not something like n^2 . The complexity thus is O(n) .
Putting all together. Continuing on the challenge to reduce the iterations on our algorithm, we have to perform the following steps: build the "index" with the information to be accessed later. iterate over the loop and fetch the additional information from the previously created "index"
If you do this
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
…
you will iterate N times in the inner loop first, then N-1, then N-2, etc., which sums to N(N-1)/2. This loop runs in O(N²), that is the square of the outer loop.
In your case, your code is equivalent to
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
c++;
since for every positive integer we have N² ≥ N and the compiler should be clever enough to notice that it makes no sense to continue running the outer loop if i is greater than N. So the complexity is indeed O(N²).
If you print N and c after your program runs, you will notice that when N gets doubled, c is almost multiplied by 4 (2²):
N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
