How to analysis?
Calculation of the following program segment x++ statement frequency:
x=1;

For (int I=0; I & lt; N ip>

For (int j=I; J & lt; N jp>

X++;

CodePudding user response:

I=0, the implementation of n
I=1, the implementation of n - 1
I=2, the implementation of n - 2
.
I=n - 1, perform 1
So the total execution n + (n - 1) + (n - 2) +... + 1=n * (n + 1)/2 times, which is O (n ^ 2)