Give the order of growth as a function of N of the running t

Give the order of growth as a function of N of the running times of each of the following code fragments

a. int sum = 0;

for(int n = N; n > 0; n /= 2)

for(int i = 0; i < n; i++)

sum++;

b. int sum = 0;

for(int i = 1; i < N; i *= 2)

for(int j = 0; j < i; j++)

sum++;

c. int sum = 0;

for(int i = 1; i < N; i *= 2)

for(int j = 0; j < N; j++)

sum++;

Solution

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

We have two loops:
   1. outer for loop runs for log(N) times, since in every iteration we are dividing n by 2
   2. inner for loop: runs for i=0 to n for each value of n

   so, T(n) = N + N/2 + N/4 + N/8 + N/16 + ........ logn times

   so, this is geometric sum of logN terms

   = O(N^(logN))

b. int sum = 0;
for(int i = 1; i < N; i *= 2)
for(int j = 0; j < i; j++)
sum++;

This is also same as part (a), here instead of dividing we are multiplying by 2

so same time complexity

c. int sum = 0;
for(int i = 1; i < N; i *= 2)
for(int j = 0; j < N; j++)
sum++;

THis is slightly different from part (a) and (b)

Here for every value of i from outer loop, we are running inner loop n times

so, N + N + N+ ..........+ logN times

Big-O: O(NlogN)