For문과 While문 중첩 코드에서의 시간복잡도

void loop (int n, int arr[])
{
	int j = 0;
	
    for(int i=0; i<n; ++i)
    	while(j<n && arr[i]<arr[j])
        	j++;
}

왜 j값 선언문에 탭이 두 개 들어가는거지.. 아무리 수정해도 고쳐지지 않는다 

 

for문의 경우 i값이 초기화되므로 최악의 경우 n회의 연산이 수행된다.

while문의 경우 j값이 초기화되지 않으므로 최악의 경우 n-1만큼의 연산이 수행된다. 

이 경우 총 n^2-n만큼 수행된다. 

그래서 결과적으로 시간복잡도의 값은 n(n-j) = n^2-n*j여서 결국 n^2보다 작으므로 O(n)이다. 

 

ex) 최악의 경우 가정

n이 10일 때

i는 10만큼 수행할 수 있으나

j는 9회까지 수행