Calculate the running time in Big-O notation

Khan

New Member
#1
Mã:
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.
 

Admin

Administrator
Thành viên BQT
#2
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.
 
Top