Time complexity of pseudocode fragment

Question

I don't mean to be asking for help with something simple, but I can't seem to figure out how to answer this question.

Compute the time complexity of the following program 
fragment: 
sum = 0; 
for i=1 to n do 
  for j=1 to i do 
    k = n*2 
    while k>0 do 
      sum=sum+1; 
      k = k div 2; 

I recognize that what is inside the while loop takes O(1), the while loop takes O(logn), but then I don't follow how that connects to the nested for loops, since I am used to just doing nested sigma notations for for loops.

Thanks!

Answer 1

A formal demonstration which shows step by step the order of growth of your algorithm:

Answer 2

Here are some hints on to break down this function's complexity:

1. Look at the inner loop, where k=n*2. Lets assume n=8 so k=16, k keeps being divided by 2 until it's 0 or less (i'll assume here that rounding 0.5 yields 0). So the series describing k until the end of the loop will be 16,8,4,2,1,0. try to think what function describes the number of elements in this series, if you know the first value is k.

2. You have two nested for loops, the first loop just iterates n times, then second (inner) loop iterates until it reaches the number of the iteration of the first loop (represented by i), which means at first it will iterate once, then twice, and so on until n. So the number of iterations performed by the second loop can be described by the series: 1, 2, 3, ... , n. This is a very simple arithmetic progression, and the sum of this series will give you the total number of iterations of the inner for loop. This is also the number of times you call the inner while loop (which is not affected by the number of the current iteration, as k depends on n which is constant and not on i or j).