MHB Checking the Efficiency of Function(int n) - Let's Count Key++ Executions!

[evinda]

Hello! (Wave)

I have the following function:

Function(int n){
  int key,j,k;
  for (j=2; j<=5n^3; j+=5){ 
        for (k=j; k<=3n^(2/3); k+=3){
             key++;
        }
  }
}

I want to find how many times the command

key++

is executed.

That's what I thought (Thinking) :

The outer for loop is executed $ \displaystyle{ \frac{5n^3-2+1}{5}=\frac{5n^3-1}{5}}$ times, the nested for loop is executed $ \displaystyle{ \frac{1}{3} \cdot \sum_{j=2}^{3n^{\frac{2}{3}}} 1 =\frac{1}{3} \cdot \sum_{j=1}^{3n^{\frac{2}{3}}} 1 -\frac{1}{3}=\frac{1}{3} \cdot 3n^{\frac{2}{3}}-\frac{1}{3}= n^{\frac{2}{3}}-\frac{1}{3} }$ times.

Therefore, the command is executed $\displaystyle{ \frac{5n^3-1}{5} \cdot \left ( n^{\frac{2}{3}}-\frac{1}{3} \right ) }$ times.

Could you tell me if it is right or if I have done something wrong? (Sweating)

 

[I like Serena]

Hello! (Wave)

I have the following function:

Function(int n){
  int key,j,k;
  for (j=2; j<=5n^3; j+=5){ 
        for (k=j; k<=3n^(2/3); k+=3){
             key++;
        }
  }
}

I want to find how many times the command

key++

is executed.

That's what I thought (Thinking) :

The outer for loop is executed $ \displaystyle{ \frac{5n^3-2+1}{5}=\frac{5n^3-1}{5}}$ times, the nested for loop is executed $ \displaystyle{ \frac{1}{3} \cdot \sum_{j=2}^{3n^{\frac{2}{3}}} 1 =\frac{1}{3} \cdot \sum_{j=1}^{3n^{\frac{2}{3}}} 1 -\frac{1}{3}=\frac{1}{3} \cdot 3n^{\frac{2}{3}}-\frac{1}{3}= n^{\frac{2}{3}}-\frac{1}{3} }$ times.

Therefore, the command is executed $\displaystyle{ \frac{5n^3-1}{5} \cdot \left ( n^{\frac{2}{3}}-\frac{1}{3} \right ) }$ times.

Could you tell me if it is right or if I have done something wrong? (Sweating)

Hey! (Malthe)

Let's see... suppose we substitute $n=1$... (Thinking)

 

[evinda]

Hey! (Malthe)

Let's see... suppose we substitute $n=1$... (Thinking)

Then, the command is executed once, but according to my result, it is executed $\frac{8}{15}$ times.. What have I done wrong? (Thinking)

 

[I like Serena]

Then, the command is executed once, but according to my result, it is executed $\frac{8}{15}$ times.. What have I done wrong? (Thinking)

Let's start with the outer loop.

Or rather, let's start with an intermezzo. (Emo)
Suppose you are walking along a road that is 100 meters long.
And suppose every meter there is a marker.
How many markers are there? (Thinking)

And what if the road is 99.8 meters? (Thinking)

 

[evinda]

Let's start with the outer loop.

Or rather, let's start with an intermezzo. (Emo)
Suppose you are walking along a road that is 100 meters long.
And suppose every meter there is a marker.
How many markers are there? (Thinking)

There are $100$ markers, right? (Wasntme)

And what if the road is 99.8 meters? (Thinking)

In this case, there are $99$ markers, right? (Thinking)

 

[I like Serena]

There are $100$ markers, right? (Wasntme)

Eek.
Suppose the road is 2 meters long... how many markers?

 

[evinda]

Eek.
Suppose the road is 2 meters long... how many markers?

Aren't there two markers? One at the first meter and one at the second one?

View attachment 3330

Or am I wrong? (Thinking) (Blush)

 

[I like Serena]

Aren't there two markers? One at the first meter and one at the second one?

https://www.physicsforums.com/attachments/3330

Or am I wrong? (Thinking) (Blush)

Doesn't your picture show 3 markers? (Wasntme)

 

[evinda]

Doesn't your picture show 3 markers? (Wasntme)

So, is there also a marker at the beginning of the road, before we have one meter? (Thinking)

 

[I like Serena]

So, is there also a marker at the beginning of the road, before we have one meter? (Thinking)

Yep.
One at the beginning of the road, and one every meter, including one at the end of the road. (Wasntme)

 

[evinda]

Yep.
One at the beginning of the road, and one every meter, including one at the end of the road. (Wasntme)

So, have I done a mistake at the limits of the sum? (Thinking)

 

[I like Serena]

So, have I done a mistake at the limits of the sum? (Thinking)

Before we go back to the limits of the sum...
Suppose the road is $x$ meters long and has markers at every $d$ meters.
How many markers? (Wondering)

 

[evinda]

Before we go back to the limits of the sum...
Suppose the road is $x$ meters long and has markers at every $d$ meters.
How many markers? (Wondering)

Is it maybe $\displaystyle{ \lfloor \frac{x}{d} \rfloor}+1$ ? (Thinking)

 

[I like Serena]

Is it maybe $\displaystyle{ \lfloor \frac{x}{d} \rfloor}+1$ ? (Thinking)

Yes! (Nod)

Now let's get back to the outer loop.
How many iterations? (Wasntme)

 

[evinda]

Yes! (Nod)

How could we explain that it is like that? (Thinking)

Now let's get back to the outer loop.
How many iterations? (Wasntme)

Are there then $\lfloor \frac{5n^3-2}{5} \rfloor +1$ iterations? (Thinking)

 

[I like Serena]

How could we explain that it is like that? (Thinking)

We can explain it by using the road-with-markers-principle. (Nerd)

If $x$ is a multiple of $d$, there are $\frac x d + 1$ markers.
If $x$ is not a multiple of $d$, we have to round $\frac x d$ down for a total of $\left\lfloor\frac x d\right\rfloor + 1$ markers.

Are there then $\lfloor \frac{5n^3-2}{5} \rfloor +1$ iterations? (Thinking)

Yes.
Can you simplify that expression? (Wondering)

 

[evinda]

We can explain it by using the road-with-markers-principle. (Nerd)

If $x$ is a multiple of $d$, there are $\frac x d + 1$ markers.
If $x$ is not a multiple of $d$, we have to round $\frac x d$ down for a total of $\left\lfloor\frac x d\right\rfloor + 1$ markers.

A ok.. Is this principle known? (Wasntme)

Yes.
Can you simplify that expression? (Wondering)

Is it maybe like that?

$$\lfloor \frac{5n^3-2}{5} \rfloor +1=\lfloor n^3-\frac{2}{5}\rfloor+1, \text{ and since } \frac{2}{5}<1, \lfloor n^3-\frac{2}{5}\rfloor+1=\lfloor n^3\rfloor+1$$

Or am I wrong? (Thinking)

 

[I like Serena]

A ok.. Is this principle known? (Wasntme)

The principle is known, although I'm not sure if it has a name.

Is it maybe like that?

$$\lfloor \frac{5n^3-2}{5} \rfloor +1=\lfloor n^3-\frac{2}{5}\rfloor+1, \text{ and since } \frac{2}{5}<1, \lfloor n^3-\frac{2}{5}\rfloor+1=\lfloor n^3\rfloor+1$$

Or am I wrong? (Thinking)

Suppose $n=1$...? (Wondering)

 

[I like Serena]

It is equal to: $1$, so it cannot be like that.. How could I simplify it then? (Thinking)

Let's take another look at $\left\lfloor n^3-\frac{2}{5}\right\rfloor + 1$.
$n^3$ is an integer.
Since we subtract $\frac{2}{5}$, and then round down, the result will always be 1 less.
And then we add 1 again... (Thinking)

 

[evinda]

Let's take another look at $\left\lfloor n^3-\frac{2}{5}\right\rfloor + 1$.
$n^3$ is an integer.
Since we subtract $\frac{2}{5}$, and then round down, the result will always be 1 less.
And then we add 1 again... (Thinking)

So, you mean that $ \displaystyle{ \left\lfloor n^3-\frac{2}{5}\right\rfloor=\left\lfloor n^3-1\right\rfloor }$ ?

Why is it like that? (Sweating)

 

[I like Serena]

So, you mean that $ \displaystyle{ \left\lfloor n^3-\frac{2}{5}\right\rfloor=\left\lfloor n^3-1\right\rfloor }$ ?

Why is it like that? (Sweating)

Yes, because this is what rounding down means. (Nerd)
For instance, for $n=1$ we have:
$$\left\lfloor 1-\frac{2}{5}\right\rfloor=\left\lfloor \frac{3}{5}\right\rfloor = 0$$

More generally, $\left\lfloor n^3-\frac{2}{5}\right\rfloor$ is always greater than the integer $n^3-1$ and smaller than $n^3$.
Therefore rounding down yields $n^3-1$. (Wasntme)

 

[evinda]

Yes, because this is what rounding down means. (Nerd)
For instance, for $n=1$ we have:
$$\left\lfloor 1-\frac{2}{5}\right\rfloor=\left\lfloor \frac{3}{5}\right\rfloor = 0$$

More generally, $\left\lfloor n^3-\frac{2}{5}\right\rfloor$ is always greater than the integer $n^3-1$ and smaller than $n^3$.
Therefore rounding down yields $n^3-1$. (Wasntme)

Is there an identity that we could use, to show it? (Thinking)

 

[I like Serena]

Is there an identity that we could use, to show it? (Thinking)

The floor function is defined as:
$$\lfloor x \rfloor=\max\, \{m\in\mathbb{Z}\mid m\le x\}$$

Now note that $n^3 -1 \le n^3 - \frac 25$ and that $n^3 > n^3 - \frac 25$.
So $n^3 -1$ is the largest integer less or equal than the number we're rounding down. (Wasntme)

 

[evinda]

The floor function is defined as:
$$\lfloor x \rfloor=\max\, \{m\in\mathbb{Z}\mid m\le x\}$$

Now note that $n^3 -1 \le n^3 - \frac 25$ and that $n^3 > n^3 - \frac 25$.
So $n^3 -1$ is the largest integer less or equal than the number we're rounding down. (Wasntme)

A ok.. I understand! (Nerd)

Could you also explain me why it is:

$$ \lfloor \frac{5n^3-2}{5} \rfloor +1$$

and not:

$$\lfloor \frac{5n^3-2+1}{5}\rfloor $$

? (Thinking)

 

[I like Serena]

Could you also explain me why it is:

$$ \lfloor \frac{5n^3-2}{5} \rfloor +1$$

and not:

$$\lfloor \frac{5n^3-2+1}{5}\rfloor $$

? (Thinking)

Because however long the road is, there will always be one marker at the beginning of the road.
We calculate how many markers come after by taking the length of the road, dividing by the distance between markers, and rounding down. (Wasntme)

 

[evinda]

Because however long the road is, there will always be one marker at the beginning of the road.
We calculate how many markers come after by taking the length of the road, dividing by the distance between markers, and rounding down. (Wasntme)

So, at this algorithm, do we know, for sure, that the first for loop is executed for $j=2$ and we want to calculate how many times it will be executed for $j=7$ till $j=5n^3$ ? (Thinking)

 

[I like Serena]

So, at this algorithm, do we know, for sure, that the first for loop is executed for $j=2$ and we want to calculate how many times it will be executed for $j=7$ till $j=5n^3$ ? (Thinking)

There is an exception.
That is if $5n^3$ would be smaller than $2$ (which is not the case here).
Then the loop would not be executed at all.
If that would be the case, the formula would come out as zero or negative. (Mmm)

 

[evinda]

There is an exception.
That is if $5n^3$ would be smaller than $2$ (which is not the case here).
Then the loop would not be executed at all.
If that would be the case, the formula would come out as zero or negative. (Mmm)

So, in our case, is it like that because of that what I wrote at post #26 ? (Thinking)

In which case does the formula come out negative? (Thinking)

 

[I like Serena]

So, in our case, is it like that because of that what I wrote at post #26 ? (Thinking)

Yes. (Nod)

In which case does the formula come out negative? (Thinking)

If you pick for instance $n=-1$. (Rain)

 

[evinda]

Yes. (Nod)
If you pick for instance $n=-1$. (Rain)

A ok.. (Nod) And is the inner loop executed $\displaystyle{ \lfloor \frac{3n^{\frac{2}{3}}-j}{3} \rfloor+1 }$ times, each time ? (Thinking) (Wasntme)

 

[I like Serena]

A ok.. (Nod) And is the inner loop executed $\displaystyle{ \lfloor \frac{3n^{\frac{2}{3}}-j}{3} \rfloor+1 }$ times, each time ? (Thinking) (Wasntme)

Yes. (Happy)

And before we go on, how many times is the outer loop executed? (Wondering)

 

[evinda]

Yes. (Happy)

And before we go on, how many times is the outer loop executed? (Wondering)

Isn't it executed $\lfloor n^3-1 \rfloor+1$ times? (Thinking) (Thinking)

 

[I like Serena]

Isn't it executed $\lfloor n^3-1 \rfloor+1$ times? (Thinking) (Thinking)

Yes... but you can simplify it further... (Wasntme)

 

[evinda]

Yes... but you can simplify it further... (Wasntme)

Is it :
$$ \lfloor n^3-\frac{2}{5}\rfloor = \lfloor n^3-1\rfloor$$

or

$$\lfloor n^3-\frac{2}{5}\rfloor= n^3-1$$

? (Thinking)

 

[I like Serena]

Is it :
$$ \lfloor n^3-\frac{2}{5}\rfloor = \lfloor n^3-1\rfloor$$

or

$$\lfloor n^3-\frac{2}{5}\rfloor= n^3-1$$

? (Thinking)

Those are the same! (Wasntme)

If you take the floor of an integer, it's just that integer.

 

[evinda]

Those are the same! (Wasntme)

If you take the floor of an integer, it's just that integer.

A ok! (Nod) So, the outer loop is executed $n^3-1$ times, right?

The inner loop is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{j}{3} \rfloor+1 }$ times..But.. how can we simplify it, now that $j$ is not a constant? (Thinking)

 

[I like Serena]

A ok! (Nod) So, the outer loop is executed $n^3-1$ times, right?

Nope.
Can you check the formula you had again? (Angel)

The outer loop is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{j}{3} \rfloor+1 }$ times..But.. how can we simplify it, now that $j$ is not a constant? (Thinking)

I guess you mean the inner loop.

Let's start with the first time the loop is executed.
That means $j=2$.
How many times does that make? (Wondering)

And how many times during the second time when $j=7$?

 

[evinda]

Nope.
Can you check the formula you had again? (Angel)

Oh, sorry! It is $n^3$, right? (Blush)

I guess you mean the inner loop.

(Nod) (Blush)

Let's start with the first time the loop is executed.
That means $j=2$.
How many times does that make? (Wondering)

And how many times during the second time when $j=7$?

The first time, it is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{2}{3} \rfloor+1 }=n^{\frac{2}{3}}-1+1=n^{\frac{2}{3}}$ times, when $j=7$, it is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{7}{3} \rfloor+1 = n^{\frac{2}{3}}-3+1=n^{\frac{2}{3}}-2}$ times..

Or am I wrong? (Thinking)

 

[I like Serena]

Oh, sorry! It is $n^3$, right? (Blush)

Yep. (Nod)

The first time, it is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{2}{3} \rfloor+1 }=n^{\frac{2}{3}}-1+1=n^{\frac{2}{3}}$ times, when $j=7$, it is executed $\displaystyle{ \lfloor n^{\frac{2}{3}}- \frac{7}{3} \rfloor+1 = n^{\frac{2}{3}}-3+1=n^{\frac{2}{3}}-2}$ times..

Or am I wrong? (Thinking)

Previously, we used that $n^3$ was an integer, so we could simplify the floor function.
However, this time round we have $n^{\frac{2}{3}}$, which does not have to be an integer.

 

[evinda]

Previously, we used that $n^3$ was an integer, so we could simplify the floor function.
However, this time round we have $n^{\frac{2}{3}}$, which does not have to be an integer.

So, can we not simplify the floor function now? (Thinking)

 

[I like Serena]

So, can we not simplify the floor function now? (Thinking)

Nope. We can't. (Doh)

 

[evinda]

Nope. We can't. (Doh)

(Worried)

So, is the inner loop executed $\sum_{j=2}^{3n^{\frac{2}{3}}} \left ( \lfloor n^{\frac{2}{3}}- \frac{j}{3} \rfloor+1 \right )$ times ? (Thinking)

 

[I like Serena]

(Worried)

So, is the inner loop executed $\sum_{j=2}^{3n^{\frac{2}{3}}} \left ( \lfloor n^{\frac{2}{3}}- \frac{j}{3} \rfloor+1 \right )$ times ? (Thinking)

Something like that... except that $j$ goes up with steps of $5$.

To simplify it, you might substitute $j=5i+2$... (Thinking)

What you will have, is more or less a arithmetic sequence.
For a complexity analysis, we would typically round it up to a worst case scenario. (Thinking)

 

[evinda]

Something like that... except that $j$ goes up with steps of $5$.

To simplify it, you might substitute $j=5i+2$... (Thinking)

What you will have, is more or less a arithmetic sequence.
For a complexity analysis, we would typically round it up to a worst case scenario. (Thinking)

For $j=2$, we have these values for $k$: $2,5,8, \dots, 3n^{\frac{2}{3}}$ and for $j=7$, we have these values for $k$: $7,10,13, \dots, 3n^{\frac{2}{3}}$, right? (Thinking)

So, is the inner loop maybe executed $\displaystyle{ \frac{1}{2} \cdot \left ( \lfloor \frac{ 3n^{\frac{2}{3}}-2}{3} \rfloor+1\right ) \cdot (3n^{\frac{2}{3}}-2) }$ times? (Thinking)

 

[I like Serena]

For $j=2$, we have these values for $k$: $2,5,8, \dots, 3n^{\frac{2}{3}}$ and for $j=7$, we have these values for $k$: $7,10,13, \dots, 3n^{\frac{2}{3}}$, right? (Thinking)

So, is the inner loop maybe executed $\displaystyle{ \frac{1}{2} \cdot \left ( \lfloor \frac{ 3n^{\frac{2}{3}}-2}{3} \rfloor+1\right ) \cdot (3n^{\frac{2}{3}}-2) }$ times? (Thinking)

Let's see...

The number of times the statement [m]key++;[/m] is executed is something like:
$$
N(2,5,8, \dots, 3n^{\frac{2}{3}})
+N(7,10,13, \dots, 3n^{\frac{2}{3}})
+N(12,15, \dots, 3n^{\frac{2}{3}})
+ \dots
+N(3n^{\frac{2}{3}})
$$
where $N(S)$ is the number of elements in the set $S$.
To be fair, the upper limit is a bit more complex, and slightly lower.
So if we calculate this, we'll get a number that is an upper estimate for the actual number of times.We can write this approximately (erring on the upper side, which corresponds to the "worst" case) as:
$$
\left(\frac{3n^{\frac{2}{3}} - 2}{3}+1\right)
+\left(\frac{3n^{\frac{2}{3}} - 7}{3}+1\right)
+\left(\frac{3n^{\frac{2}{3}} - 12}{3}+1\right)
+ \dots
+1
$$

How many terms are that? (Wondering)