# Thread: determining iterations in nested for loop with floor function

1. ## determining iterations in nested for loop with floor function

Sorry for all the posts, trying to prepare for upcoming algorithms course. Again, I am to determine the number of iterations given this code. So I looked at the solution and this table was provided which listed all the indices. ASSUME N is odd. How exactly do the come up with n-1/2 and n+1/2 in the table?? Its seems like on n-1th iteration, we should subsitute n-1 for i and get ((n-1)+1)/2.

the solution is

2(1+2+3+....(n-1)/2)) + (n+1)/2
everything in the solution makes sense to me except how the come up with those last two terms

2. ## Re: determining iterations in nested for loop with floor function

Let $n=2k+1$

let's look at the range of $j$'s for a given $i$

$\begin{matrix}\text{i} &\text{range of j, 1 to} \\ 1 &1 \\ 2 &1 \\ 3 &2 \\ 4 &2 \\ \vdots &\vdots \\ 2j-1 &j \\ 2j &j \\ \vdots &\vdots \\ 2k-1 &k \\ 2k &k \\ 2k+1 &k+1 \end{matrix}$

looking at this table we see we have a total of

$2(1+2+3 + \dots + k)$

for the first $2k$ terms, and then a final term of $k+1$

$k=\dfrac{n-1}{2}$ so this becomes

$2\left(1 + 2 + 3 + \dots + \dfrac{n-1}{2}\right)+\dfrac{n-1}{2}+1 =$

$2\left(1 + 2 + 3 + \dots + \dfrac{n-1}{2}\right)+\dfrac{n+1}{2}$

3. ## Re: determining iterations in nested for loop with floor function

thank you for the explanation, but I am still kind of confused.
1) So how is j being calculated? Are you applying the floor function or does it get applied after?
2) i guess i am still not really understanding how you are arriving at that last term

4. ## Re: determining iterations in nested for loop with floor function

Originally Posted by mdm508
thank you for the explanation, but I am still kind of confused.
1) So how is j being calculated? Are you applying the floor function or does it get applied after?
2) i guess i am still not really understanding how you are arriving at that last term
really?

j goes from $1 \to \dfrac {i+1}{2}$

can you not calculate $\dfrac {i+1}{2}$ for a given $i$ ?

any time you see positive iterators being divided in this fashion you use the floor function, just drop the fractional part

the last term arises from your specification that $n$ is odd, look at the table again

5. ## Re: determining iterations in nested for loop with floor function

Originally Posted by romsek

any time you see positive iterators being divided in this fashion you use the floor function, just drop the fractional part
okay, i did not know, i think that is what was throwing me off about this whole thing. thanks

6. ## Re: determining iterations in nested for loop with floor function

alright! definitely understand it now, think sleeping on it helped thanks