1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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