큰 오 특정 기능 세타 표기법 ... F를 평가하는 단계 (n)은 세타 (N) 인 경우 실행 시간

Question

i = 1; 
sum = 0; 
while (i <= n) 
     do if (f(i) > k) 
      then sum += f(i); 
      i = 2*i; 

겠습니까이 될 O의 주행 시간 (N은^3) 때문에 함수가 호출 될 가능성이 있거나 함수가 O (n) 일 가능성이 있습니까? 또는 그것이 우리가 알고있는 정보이기 때문에 그것은 쎄타의 측면에서 뭔가입니까? 나는 매우 내가 변수 복식마다 =>이 LOG2 (N) 시간에 N에 도달 할 것 ... 이것에

Answer 1

을 상실하고있다. f의 평가가 완료됩니다 Log2 (n) times => 함수 시간 복잡도는 O (N x LogN)입니다. F (i)를 계산하는 복잡도 O (I)가있는 경우

사실, 그 시간 복잡도는 :

1 + 2 + 4 + ... + 2^(Log2(n)) = n (there are Log2(n) steps) => O(n)