MHB Does the variable take these values?

[evinda]

Hello! (Wave)

If we have the following for loop:

 for (i=8^{n-1}; i<8^n; i+=1)

(where $n$ is an integer)

does $i$ take the values $8^{n-1}, 8^{n-1}+1, \dots, 8^n-1$, or am I wrong? (Thinking)

 

[Evgeny.Makarov]

You are correct. Note, however, that this precise syntax would not work in C, C++, Java and other C-like languages.

 

[evinda]

You are correct. Note, however, that this precise syntax would not work in C, C++, Java and other C-like languages.

Nice, thank you! (Smile)

It should be also $n \geq 1$, right? (Thinking)

- - - Updated - - -

Or do we not have to take restrictions for $n$ ? (Thinking)

 

[Evgeny.Makarov]

It should be also $n \geq 1$, right? (Thinking)

Or do we not have to take restrictions for $n$ ? (Thinking)

The loop will not terminate unless $n$ is a positive integer.

Edit: As I remark later, the loop will always terminate.

 

[evinda]

The loop will not terminate unless $n$ is a positive integer.

So, can I just say that $i$ takes the values $8^{n-1}, 8^{n-1}+1, \dots, 8^n-1$ times, so the for loop will be executed $7 \cdot 8^{n-1}$, or do I have to say that $i$ takes these values, only if $n \geq 1$ ? (Thinking)

 

[Evgeny.Makarov]

First, my remark about termination was wrong. The loop will terminate in any case because the loop guard is $i<8^n$ and not $i=8^n$.

So, can I just say that $i$ takes the values $8^{n-1}, 8^{n-1}+1, \dots, 8^n-1$ times, so the for loop will be executed $7 \cdot 8^{n-1}$, or do I have to say that $i$ takes these values, only if $n \geq 1$ ? (Thinking)

What you said is correct when $n\ge 1$ and $n$ is an integer. Determining the precise number of iterations when $8^{n-1}$ or $8^n$ is not an integer requires some thought (though it's not hard). Do you really need this?

 

[evinda]

First, my remark about termination was wrong. The loop will terminate in any case because the loop guard is $i<8^n$ and not $i=8^n$.

What you said is correct when $n\ge 1$ and $n$ is an integer. Determining the precise number of iterations when $8^{n-1}$ or $8^n$ is not an integer requires some thought (though it's not hard). Do you really need this?

I am given this algorithm:

Function(int n){
  int key=1, j,t,x;
  for (j=2*n; j<=8*n; j++){ 
        for (t=8^(n-1); t<8^n; t++){
             for (x=3; x<55; x++){
                  key++;
             }
        }
  }
}

and I want to find how many times the command key++ is executed.

The first for is executed $6n+1$ times, the secod for is executed $7 \cdot 8^{n-1}$ times and the third one, $52$ times. So, the command is executed $(6n+1) \cdot 7 \cdot 8^{n-1} \cdot 52$ times.

Do I have to say that it is executed only when $n \geq 1$ ? (Thinking)

 

[Evgeny.Makarov]

The first for is executed $6n+1$ times, the secod for is executed $7 \cdot 8^{n-1}$ times and the third one, $52$ times. So, the command is executed $(6n+1) \cdot 7 \cdot 8^{n-1} \cdot 52$ times.

Do I have to say that it is executed only when $n \geq 1$ ?

Yes, your analysis is correct when $n\ge 1$ (and the argument type says that $n$ is integer). If $n=0$, then the first and second loops execute 1 time each, so [m]key++[/m] is executed 52 times. If $n<0$, then the first loop is never executed, so [m]key++[/m] is executed 0 times.

 

[evinda]

Yes, your analysis is correct when $n\ge 1$ (and the argument type says that $n$ is integer). If $n=0$, then the first and second loops execute 1 time each, so [m]key++[/m] is executed 52 times. If $n<0$, then the first loop is never executed, so [m]key++[/m] is executed 0 times.

So, if $n=0$, does $t$ take only the value $\frac{1}{8}$ and then the for loop terminates? (Thinking)

 

[Evgeny.Makarov]

Yes, because $8^{-1}+1=\frac{1}{8}+1>1=8^0$.

 

[evinda]

Yes, because $8^{-1}+1=\frac{1}{8}+1>1=8^0$.

I understand! (Nod)

So, do I have to distinguish the cases:

• $n=0$
• $n \geq 1$

and find a formula for each case? (Thinking)

 

[Evgeny.Makarov]

So, do I have to distinguish the cases:

• $n=0$
• $n \geq 1$

Yes, and $n<0$.

and find a formula for each case?

In each case, formulas have already been written explicitly in this thread.

Edit: My guess is that the problem authors assumed that $n\ge 1$, but I can't be sure.

 

[evinda]

Yes, and $n<0$.

In each case, formulas have already been written explicitly in this thread.

Edit: My guess is that the problem authors assumed that $n\ge 1$, but I can't be sure.

Nice! Thank you very much! (Smile)