Calculate the running time in Big-O notation


New Member
1 int sum=0;
2 long start = System.currentTimeMillis();
3 for (int i = 1; i <= N; i++) {
4 for (int j = 1; j <= N; j++) {
5 sum=sum+1;}}
6 long stop = System.currentTimeMillis();
7 long elapsed = (long)(stop - start);
I am stuck on this question I know lines 1,2,5,6 and 7 are primitive operations they run at O(1) constant time. I am having doubt about the loops I think it is O(n^2) can anyone elaborate on this thanks.


Thành viên BQT
You are right, one for loop alone is O(n) because it's running time is linearly proportional to the size of the input, and together with the second loop it is O(n^2) because you repeat an O(n) function n times.