0
I’m learning how to calculate the complexity of algorithms using Big-O notation, but I’m having difficulties with the algorithm below:
a=0
for(int i = n; i>0; i -=2){
for(int j = i+1; j<=n;j+=1){
a++;
}
}
If you could explain to me how to solve it, I’d appreciate it.
3
For each batch loop, we usually assume a factor in asymptotic notation and of course the impulse leads us to believe that cases like this are O(n*n)=O(n²), as if each loop applied a linear factor, but sometimes it is not so.
For example, applying quicksort to loops (not recursions) results in predominantly O(n*log(n)), even being able to implement with two loops and in the worst case being O(n²). Moreover, mergesort in well-implemented loops is always O(n*log(n)), either with two loops in batch, or with three. So, let’s analyze.
In the loop of i, we find that it performs 1x if n=1 or n=2, 2x if n=3 or n=4, from then on linearly, as it walks from two units per cycle to a fixed stop condition. If n<=0, executes 0x. I mean, the number of loop cycles i is max(0,ceil(n/2)), to simplify is understood as n/2.
Already in the loop of j, the number of times it executes is simply (n-i)x, for in the first it executes 0x, in the second, 2x, in the third, 4x and so on, until the end of the loops in 'i' that reduce this index by two. The number of cycles in j is n-i.
So the series is n+(n-2)+(n-4)+...+3+1 (if n is unique) or n+(n-2)+(n-4)+...+4+2 (if n for par). This results in the two formulas:
when n is even or
when n is unique.
Both result in the same asymptotic formula, which is the complexity of the algorithm: O(n²).
Browser other questions tagged algorithm mathematics
You are not signed in. Login or sign up in order to post.
Because there are two loops, one inside the other, the complexity must be O(N2), but I don’t understand the subject. You have this question that may help you: https://answall.com/questions/56836
– Costamilam