CODEWITHSUNDEEP
algorithmloopstime-complexity
gmad
gmad

Reputation: 13

Loop Analysis - Analysis of Algorithms

This question is based off of this resource http://algs4.cs.princeton.edu/14analysis.

Can someone break down why Exercise 6 letter b is linear? The outer loop seems to be increasing i by a factor of 2 each time, so I would assume it was logarithmic...

From the link:

int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;

Upvotes: 1

Views: 180

Answers (2)

Anup
Anup

Reputation: 2434

Yes its simple See the value of n is decreasing by half each time and I runs n times.

So for the first time i goes from 1 to n next time 0 to n/2 and hence 0 to n/k on kth term.

Now total time inner loop would run = Log(n)

So its a GP the number of times i is running. with terms

n,n/2,n/4,n/8....0

so we can find the sum of the GP

2^(long(n) +1)-1  / (2-1)

2^(long(n)+1) = n
hence n-1/(1) = >O(n)

Upvotes: 0

amit
amit

Reputation: 178411

This is a geometric series. The inner loops runs i iterations per iteration of the outer loop, and the outer loop decreases by half each time.

So, summing it up gives you:

n + n/2 + n/4 + ... + 1

This is geometric series, with r=1/2 and a=n - that converges to a/(1-r)=n/(1/2)=2n, so:

T(n) <= 2n

And since 2n is in O(n) - the algorithm runs in linear time.

This is a perfect example to see that complexity is NOT achieved by multiplying the complexity of each nested loop (that would have got you O(nlogn)), but by actually analyzing how many iterations are needed.

Upvotes: 3

Related Questions