Counting Times t+=8 Executed in Algorithm Fun

[evinda]

Hi! (Smile)

Given the following algorithm, I want to find how many times the command t+=8 is executed.

Function Fun(int m){
int j,k,t=1;
for (j=0; j<=4n^2; j+=4){
     for (k=j; k<=4*sqrt(n); k+=4){
          t+=8;
     }
}
}

The outer loop is executed $\lfloor \frac{4n^2}{4} \rfloor+1=n^2+1$ times, right?
But, after $j= 4 \sqrt{n}$, the inner loop isn't executed.
So, do I have to count the times that the outer loop is executed, till $j= 4 \sqrt{n}$ ? (Thinking)

 

[evinda]

I tried to find a general formula, by using different values for $n$ and I concluded that the command t+=8; is executed $\sum_{j=0}^{\lfloor \sqrt{n} \rfloor } \left ( \lfloor \sqrt{n} \rfloor-j+1 \right )$ times.

But.. how could I explain formally that the command is executed $\sum_{j=0}^{\lfloor \sqrt{n} \rfloor } \left ( \lfloor \sqrt{n} \rfloor-j+1 \right )$ times?

 

[I like Serena]

I tried to find a general formula, by using different values for $n$ and I concluded that the command t+=8; is executed $\sum_{j=0}^{\lfloor \sqrt{n} \rfloor } \left ( \lfloor \sqrt{n} \rfloor-j+1 \right )$ times.

But.. how could I explain formally that the command is executed $\sum_{j=0}^{\lfloor \sqrt{n} \rfloor } \left ( \lfloor \sqrt{n} \rfloor-j+1 \right )$ times?

Here's a method to count this. (Sweating)The highest number in the inner loop that is reached, is:
$$
4\left\lfloor \frac{4\sqrt n}{4} \right\rfloor = 4\lfloor \sqrt n\rfloor
$$
This is lower than the highest number of the outer loop, which is $4n^2$ (edited).

So the number of times the inner loop is executed is:
$$
N(0,4,...,4\lfloor \sqrt n\rfloor) + N(4,...,4\lfloor \sqrt n\rfloor) + ... + N(4\lfloor \sqrt n\rfloor) =\sum_{i=0}^{\lfloor \sqrt{n} \rfloor } \left ( \lfloor \sqrt{n} \rfloor-i+1 \right )
$$
where $N(S)$ is the number of elements in set $S$.This is an arithmetic sequence with $\lfloor \sqrt{n} \rfloor+1$ terms.
Therefore the total number of iterations of the inner loop is:
$$
\frac 1 2 (\lfloor \sqrt{n} \rfloor+1)\big((\lfloor \sqrt{n} \rfloor+1) + 1\big)
=\frac 12(\lfloor \sqrt{n} \rfloor^2+3\lfloor \sqrt{n} \rfloor + 2)
$$

So the order is $O(\frac 1 2 n^2)$. (Nerd)

 

[evinda]

The highest number in the inner loop that is reached, is:
$$
4\left\lfloor \frac{4\sqrt n}{4} \right\rfloor = 4\lfloor \sqrt n\rfloor
$$

Could you explain me how you found the highest number that is reached in the inner loop?

I thought that we would calculate it, using this formula:

$$\lfloor \frac{4 \sqrt{n}-j}{4} \rfloor+1$$

for $j=0$.. Am I wrong? (Thinking)

 

[I like Serena]

Could you explain me how you found the highest number that is reached in the inner loop?

I thought that we would calculate it, using this formula:

$$\lfloor \frac{4 \sqrt{n}-j}{4} \rfloor+1$$

for $j=0$.. Am I wrong? (Thinking)

You are referring to the highest number of iterations. (Shake)
I was referring to the highest number that $k$ can become. (Nod)It is given that $k \le 4\sqrt n$ while $k$ is always a multiple of $4$.
What is the highest multiple of $4$ that is less or equal than $4\sqrt n$? (Wondering)

 

[evinda]

You are referring to the highest number of iterations. (Shake)
I was referring to the highest number that $k$ can become. (Nod)

A ok! (Nod)

It is given that $k \le 4\sqrt n$ while $k$ is always a multiple of $4$.
What is the highest multiple of $4$ that is less or equal than $4\sqrt n$? (Wondering)

The highest multiple of $4$ that is less or equal than $4\sqrt n$ is $4 \lfloor \sqrt{n} \rfloor$, right? (Thinking)

 

[I like Serena]

The highest multiple of $4$ that is less or equal than $4\sqrt n$ is $4 \lfloor \sqrt{n} \rfloor$, right? (Thinking)

Yup! (Nod)

 

[evinda]

The highest number in the inner loop that is reached, is:
$$
4\left\lfloor \frac{4\sqrt n}{4} \right\rfloor = 4\lfloor \sqrt n\rfloor
$$
This is lower than the highest number of the outer loop, which is indeed $n^2+1$.

Isn't the highest number of the outer loop equal to $4n^2$ ? Or am I wrong? (Worried)

 

[I like Serena]

Isn't the highest number of the outer loop equal to $4n^2$ ? Or am I wrong? (Worried)

You are right. (Doh)

 

[evinda]

The highest number in the inner loop that is reached, is:
$$
4\left\lfloor \frac{4\sqrt n}{4} \right\rfloor = 4\lfloor \sqrt n\rfloor
$$
This is lower than the highest number of the outer loop, which is $4n^2$ (edited).

Does this mean that the inner loop will be executed while $j \leq 4 \lfloor \sqrt{n} \rfloor$ ? (Thinking)

 

[I like Serena]

Does this mean that the inner loop will be executed while $j \leq 4 \lfloor \sqrt{n} \rfloor$ ? (Thinking)

Depends on what you mean by executed.
Taken literally, the inner loop is executed more often.
But since the starting number is higher than the ending number, its body, the statement [m]t += 8;[/m], is not executed. (Nerd)

 

[evinda]

Depends on what you mean by executed.
Taken literally, the inner loop is executed more often.
But since the starting number is higher than the ending number, its body, the statement [m]t += 8;[/m], is not executed. (Nerd)

So, after $j$ has taken the value $4 \lfloor \sqrt{n} \rfloor$, we chek each time if $j$ is less or equal to $4 \sqrt{n}$, but since this condition will not be true for any $j$, the command $t+=8;$ will not be executed? (Thinking)

Or have I understood it wrong?

 

[I like Serena]

So, after $j$ has taken the value $4 \lfloor \sqrt{n} \rfloor$, we chek each time if $j$ is less or equal to $4 \sqrt{n}$, but since this condition will not be true for any $j$, the command $t+=8;$ will not be executed? (Thinking)

Or have I understood it wrong?

Yep. That's it. (Nod)

 

[evinda]

Yep. That's it. (Nod)

Nice! Thank you very much! (Party)