I want to ask for this question, what is the algorithm analysis for this? outer loop will execute for n 2 times how we determine the inner loop? is it (n 1)/2

for(int i = 0;i <= n;i  )
    for(int j = n;j>i;j--)

CodePudding user response：

The outer loop has n 1 iterations.

The inner loop has n - i iterations.

To find the overall time complexity, you have to sum the iterations of the inner loop for all the values of i:

n   (n - 1)   (n - 2)   ...   1 = (n 1)*n/2 = O(n^2)

CodePudding user response：

@Eran's answer works, but it's easier to figure this out without calculating exactly how many iterations there are of the inner loop.

For n/2 iterations of the outer loop (the ones for small i), the inner loop iterates at least n/2 times. So in total you have at least (n/2)² = n²/4 = O(n²).

We can also see that the outer loop iterates at most n times, and the inner loop at most n times for all of those, so in total you have at most n² inner iterations, which is also O(²)