Is this allowed in substitution

[Ad2d]

Homework Statement

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

The Attempt at a Solution

Here we assume n = 2^k

This is my way:

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

= 4(f(2^k-2) * (2*2^k) - 3
:
:
= 2^j*f(2^k-j) + j2^k - (j-1)

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

j2^j - (j-1) = j2^j - j + 1 = j(2^j)

The TA way

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

she put

= 4(f(2^k-2) * (2*2^k) - 2² + 1

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

Is her way correct where instead of putting the -3 she put the -2² + 1 ?

 

[jhicks]

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

I don't understand what you wrote. Can you rephrase? I fail to see the "recurrence".

 

[HallsofIvy]

Homework Statement

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

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

The Attempt at a Solution

Here we assume n = 2^k

This is my way:

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

Why k-1? If n= e^k, tnen f(n)= f(2^k-1). How did you reduce it to "f(k-1)"? Putting n= 2^k would give n/2= 2^k-1. Is that what you meant?
Are you relabeling f(n)= f(2^k) 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.

= 4(f(2^k-2) * (2*2^k) - 3
:
:
= 2^j*f(2^k-j) + j2^k - (j-1)

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

j2^j - (j-1) = j2^j - j + 1 = j(2^j)

The TA way

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

she put

= 4(f(2^k-2) * (2*2^k) - 2² + 1

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

Is her way correct where instead of putting the -3 she put the -2² + 1 ?

 

[Ad2d]

Sorry for the confusion. You right when you stated that when n=2^k that f(n/2) becomes f(2^k/2) which goes to f(2^k-1).

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

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


I mean naturally - 2² + 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 into 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.