Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Is this allowed in substitution

  1. Oct 26, 2008 #1
    1. The problem statement, all variables and given/known data
    I have recurrence relation problem and what to ask would my way be just as correct as the TA did the solution:

    f(n) = 0, n=1 and 2f(n/2) + n -1

    3. The attempt at a solution

    Here we assume n = 2k

    This is my way:

    f(k-1) = 2[2f(2k-2)*2k-1-1] + 2k - 1

    = 4(f(2k-2) * (2*2k) - 3
    = 2j*f(2k-j) + j2k - (j-1)

    Guess: j=k
    2j*f(2j-j) + j2j - (j-1)
    2jf(1)+ j2j - (j-1)

    j2j - (j-1) = j2j - j + 1 = j(2j)

    The TA way

    She did the same thing I did but in the part where we have
    = 4(f(2k-2) * (2*2k) - 3

    she put

    = 4(f(2k-2) * (2*2k) - 22 + 1

    where my guess came to be j(2j) she gets 2j(j-1) +1

    Is her way correct where instead of putting the -3 she put the -22 + 1 ?
    Last edited: Oct 26, 2008
  2. jcsd
  3. Oct 26, 2008 #2
    I don't understand what you wrote. Can you rephrase? I fail to see the "recurrence".
  4. Oct 27, 2008 #3


    User Avatar
    Science Advisor

    Do you mean f(n)= 2f(n/2)+ n- 1?

    Why k-1? If n= ek, tnen f(n)= f(2k-1). How did you reduce it to "f(k-1)"? Putting n= 2k would give n/2= 2k-1. Is that what you meant?
    Are you relabeling f(n)= f(2k) as f(k)? That can be done but you must say so: and it would be better to use a different symbol as you now have a different function: let g(k)= f(2[/sup]k[/sup]). And, of course, since most natural numbers are NOT powers of 2, letting k be a natural number will not give all values of n.

  5. Oct 27, 2008 #4
    Sorry for the confusion. You right when you stated that when n=2k that f(n/2) becomes f(2k/2) which goes to f(2k-1).

    For the f(n-1) I may have skipped a step when substitution. I meant to say:
    f(k) =2f(2k-1). + 2k -1

    then after that I started my substitution. My qeustion was that when I did my first subsititution I got: 4(f(2k-2) * (2*2k) - 3 where the TA got 4(f(2k-2) * (2*2k) - 22 + 1

    I mean naturally - 22 + 1 = -3 but can you do that in substitution? It seems like you are forcing the problem.

    Also, you are right that if "letting k be a natural number will not give all values of n". The reason, I believe, that we are letting that happen is because this is a merge sort recursion (sorry again, did not realize that I post in my first post) and that you what any size list that is going in to merge sort to be divide fairly even. I do not know why, but professor could have but the floor symbol or ceiling symbol on the n/2 and that would do it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook