Results 1 to 6 of 6

Thread: determining iterations in nested for loop with floor function

  1. #1
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    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.
    determining iterations in nested for loop with floor function-screen-shot-2016-12-21-10.37.46-am.pngdetermining iterations in nested for loop with floor function-screen-shot-2016-12-21-10.38.29-am.png
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,401
    Thanks
    2290

    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}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,401
    Thanks
    2290

    Re: determining iterations in nested for loop with floor function

    Quote Originally Posted by mdm508 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: determining iterations in nested for loop with floor function

    Quote Originally Posted by romsek View Post

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    39
    Thanks
    1

    Re: determining iterations in nested for loop with floor function

    alright! definitely understand it now, think sleeping on it helped thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. determining number of iterations in a for loop
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 21st 2016, 08:17 AM
  2. Replies: 3
    Last Post: Dec 21st 2016, 05:35 AM
  3. Floor function nested division
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 7th 2012, 03:39 PM
  4. Replies: 3
    Last Post: Jun 22nd 2012, 07:43 AM
  5. Replies: 1
    Last Post: Dec 3rd 2009, 08:45 AM

/mathhelpforum @mathhelpforum