Analysis of Algorithms | Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

매개 변수의 증가폭이 1씩 증가할 때의 시간 복잡도

void fun(int n) 
{ 
   int j = 1, i = 0; 
   while (i < n) 
   { 
       // Some O(1) task 
       i = i + j; 
       j++; 
   } 
} 

위 코드의 반복문 매개변수는 증가 폭이 1, 2, 3, 4로 1씩 증가하고 있다. 그러므로 $k$번 반보갈 때 $\cfrac{k(k+1)}{2}$이 된다. 즉, $\cfrac{k^2+k}{2}\le n$ 조건을 만족할 때까지 코드 실행을 반복한다. 따라서, 위 코드의 시간 복잡도는 $O(\sqrt{n})$이다.

참고자료

1. Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..