Summation with variables

Question

I'm trying to calculate how many times the * will be printed in my screen:

print( int n ) {
int i = n;
while ( i > 0 ) {
 
    for( int j = 1; j < n; j++ ) {
     
        printf( "*" );   
    }
    i = Math.floor( i / 2 );
}

I can identify that the sequence is the following:

|      i     |      j     |    iterations    |
|   i = n;   | j { 1..n } | n - 1 iterations |
| i = n / 2; | j { 1..n } | n - 1 iterations |
| i = n / 4; | j { 1..n } | n - 1 iterations |
...
|   i = 2;   | j { 1..n } | n - 1 iterations |
|   i = 1;   | j { 1..n } | n - 1 iterations |
|   i = 0;   |   --//--   |   -----//-----   |

Therefore:

{ n    , n/2  , n/4  , n/8  , ..., 2, 1 }    
{ n/2^0, n/2^1, n/2^2, n/n^3, ..., 2, 1 }

I was trying to use a P.G. to figure it out, but I opted to use Summation instead.

So my Summation is: Summation

But I think I got it wrong, because I can't seem to reach a conclusion that n/2^n-1 will be 1

If anyone have any idea on how I would go from there, or if I'm incorrect on my steps, I'd like to know.

Answer 1

This program, on each iteration (i.e. each time the j-loop runs), prints $n-1$ times. This does not change when the input changes.

What does change with changes in input is how many times the j-loop runs. It runs $a$ times, where $a = 1 + \operatorname{floor}(\log_2 n)$. For instance, when n=5, the j-loop runs $1+\operatorname{floor}(\log_2 5) = 3$ times. Here's how we know this:

Because i is divided by 2 over and over, we can say that it is of the form $2^q$. So if i is set to n=9 at the beginning, we have

i = 9

j-loop #1

i = 4

j-loop #2

i = 2

j-loop #3

i = 1

j-loop #4

i = 0

We started with $n = 9 = 2^{3.1699}$, and we ran the j-loop $3 + 1$ times! So we see that with $n = 2^q$, we run the j-loop $1 + \operatorname{floor}(q)$ times. But the exponent in $2^q = n$ is given by $q = \log_2(n)$, which means that in total, the j-loop runs $1 + \log_2(n)$ times.

Now think of a summation as a for loop. Doing for(int i=1; i <= n+1; i++) is the same as for(int i=0; i <= n; i++) when i is used only as an iterator and doesn't actually take part in the calculation of the thing we're summing. In the same vein, we can turn our summation from

$$\sum_{k=1}^{1 + \operatorname{floor}(\log_2 n)} (n-1)$$

into

$$\sum_{k=0}^{\operatorname{floor}(\log_2 n)} (n-1) \tag{isn't that prettier?}$$

Note that $\operatorname{floor}(\log_2 n)$ and $(n-1)$ are constants (for a given $n$). Think about what happens when we do summations of constants. Consider $$\sum_{k=0}^n c$$

$n$ and $c$ are both constants, and $k$ doesn't have anything to do with the calculations that take place each iteration (i.e. we are using it as nothing more than an iterator), so we know that $\sum_{k=0}^n c = \text{[number of times that we iterate]} * c = (n+1)c$.

Extending this to our summation, we have

$$\sum_{k=0}^{\operatorname{floor}(\log_2 n)} (n-1) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} (n-1) = (\lfloor \log_2 n \rfloor + 1)(n-1)$$