Stavrosnco - 9 months ago 55

Java Question

I am working through a section of a text on determining complexity of nested loops using recurrence relations. In this particular example I am trying to determine how many times the count variable will be incremented as a function of n.

This is the loop I am analyzing:

`for (int i = 1; i <= n; i++) {`

int j = n;

while (j > 0) {

count++;

j = j / 2;

}

}

I think I understand that the first line would equate simply to n since it only executes for each value of n but it's the rest of it that I'm having trouble with. I think the answer would be something like n(n/2) except that this example is using integer division so I'm not sure how to represent that mathematically.

I've run through the loop by hand a few times on paper so I know that the count variable should equal 1, 4, 6, 12, 15, and 18 for n values of 1-6. I just can't seem to come up with the formula... Any help would be greatly appreciated!

Answer Source

The loop executes for `n`

in the range `[1, n]`

. It divides by 2 each time for the `j`

variable, which is set to n, so the number of time the inner loop executes is `floor(l2(n)) + 1,`

where l2 is the binary log function. Add up all such values from 1 to n (multiply by `n`

).