# 수행시간 측정
## 문제
주어진 2가지 알고리즘을 비교하고, 실제 수행시간 차이가 나는 이유를 주석으로 설명하시오.
## 뼈대코드
```
public class Sum {
public static void main(String[] args) {
int[] sampleCounts = { 1, 10, 100, 1000, 10000, 100000 };
long start = 0;
long end = 0;
int sum = 0;
for (int n : sampleCounts) {
System.out.println("=================================");
// sumA(n)
start = System.nanoTime();
sum = sumA(n);
end = System.nanoTime();
System.out.printf("sumA(%d): %d ns\n", sum, end - start);
// sumB(n)
start = System.nanoTime();
sum = sumB(n);
end = System.nanoTime();
System.out.printf("sumB(%d): %d ns\n", sum, end - start);
}
}
private static int sumA(int n) {
return n * (n + 1) / 2;
}
private static int sumB(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
}
```
## 출력 예
```
=================================
sumA(1): 6305 ns
sumB(1): 9714 ns
=================================
sumA(55): 1005 ns
sumB(55): 1398 ns
=================================
sumA(5050): 769 ns
sumB(5050): 3229 ns
=================================
sumA(500500): 1135 ns
sumB(500500): 43411 ns
=================================
sumA(50005000): 742 ns
sumB(50005000): 204282 ns
=================================
sumA(705082704): 718 ns
sumB(705082704): 2966879 ns
```
## 힌트
시간 복잡도
```
O(1) < O(N) < O(logN) < O(NlogN) < O(N^2) < O(N^3) < O(2^N)
```