Time Complexity for loop

问题:

I was trying to find the time complexity for a for loop. below is loop detail.

for(int i=N;i>1;i=i/2)
{
   for(int k=0;k<i;k++){
     sum++;
   }
}

Below is any find for the problem. Please correct me if i am going worng.

Inner loop will be exceute N+N/2+N/4+N/8....

so tn=ar^(n-1). So replacing Tn=1, a=N and r=1/2

1=N(1/2)^(n-1)

therefore

1/2N=(1/2)^n

So sum of inner loop is a GP. Sn=a(1-r^n)/(1-r) Replacing a=N,r=1/2, we get

Sn=N(1-(1/2N))/(1-1/2)

therefore Sn=2N-1

I am not sure if complexity is N.

Please help

Thanks.

回答1:

Below is the formal way (Sigma Notation) to infer the order of growth related to your algorithm (corroborated with experiments, using C's MinGW2.95 compiler).