빅 오 표기법을 사용하는데 예를 들어서
for(int i=0; i<n ; i++)
for(int j=1; j<=n ; j*=2)
count ++;
이런 이중 for문이 있다면,
여기서 비교횟수, 대입 횟수, 덧셈연산 횟수를 총 몇번이나 하는걸까요?
따라서 T(n)은 어떻게 되며 이것을 빅오 표기법으로 나타낸다면 어떻게 표기가 가능할까요?
sehongpark님의 답변
## 답변
특정 비율로 연산이 감소되는 경우 logN으로 간주합니다.
```
for (int i = 0; i < n ; i++) // n번 반복
for (int j = 1; j <= n; j *= 2) // 0.5 * n번 반복
count++; // 0.5 * n번 반복
```
따라서 두 번째 반복문의 횟수가 데이터의 크기 N의 절반이므로, O(NlogN)이 될 듯합니다.