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

[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)