는

Question

은 행 큰 세타주세요 바인딩

N 반복에 대한 실행 루프의 첫 번째. 그런 다음 첫 번째 for 루프 내의 for for 루프는 n 반복 동안 실행되어 O (n^2)를 제공합니다.

else 문에서 while 루프는 n 회 반복 실행되고 k = k/2는 O (nlogn)을 제공하는 logn 시간 동안 실행됩니다. 그러면 전체가 n^2 + nlogn처럼 보일 것이며 더 큰 실행 시간을 취함에 따라 답은 theta n^2가 될 것입니까?

Answer 1

은 선형 n의 n보다 작지 않으므로 결과는 O(nlogn)입니다. else 브랜치가 우세 할 것이다.

예 :

n= 10000 
after i=100 the else part will be calculated instead of the inner for loop