界環路

Question

緊運行時有人可以幫我找到開往這個循環的緊運行時：

for(c4=0, i=1; i<=n; i = 2*i) 
    for(j=1; j<= i; j++) 
     c4++; 

我不知道用2做*我在外環，我認爲內循環類似於O（i-1）/ 1，並且根據n將會是O（n-1），因爲這個時候我是< = n。

在此先感謝。

Answer 1

外環將運行log(N)次。對於每個外部循環，內部循環將運行i次。並且i從1，2，4，8，16，...，log（N）開始。

所以總數約爲2 ^（log（N）） - 1，它是O（N）