Recurrence relation problem

[algorithmist]

How to solve this recurrence relation

T(n)= 3 T(n/2) + n lgn

I am not convinced that we can apply Master method.And thus when i solve it using iterative approach i am stuck in logarithmic series formed in above.any help would be appreciated.

[superbonzo]

no, the master theorem applies in this case, so the asymptotics is computable; regarding the full solution of the equation, I can think of two ways:

1) easy but uncertain: make an ansatz from the asymptotic form and solve for the parameters ...

2) sure but tricky: recast the equation in difference equation form ( eg. use the substitution k = log(n)/log(2) ), then linearize the equation ( eg. write the step operator as a 3x3 matrix ... ), then the tricky part: the matrix is not diagonalizable, so you should find a continuous curve passing from the matrix that is diagolizable in an open subset of its domain containing the preimage of the matrix, then diagolize, take the nth power, take the limit and return back to the original equation. As I said, it's tricky but it works :)

EDIT:

3 ? ) now that I have the solution in front of me ( I used method 2 ) I suspect there are easier ways ... so, you could wait and see if someone find them ... :)

EDIT 2:

indeed, method 1 is easier then I thought: try substituting n with n/2 in n*log(n), then given the asimptotics bound the correct ansatz solution should be obvious ...

[nuzzle]

2) sure but tricky: recast the equation in difference equation form


It's not that hard.

One can note that T is valid when n is a a power of 2 only, like T(2), T(4), T(8), T(16) etcetera.

This means the original T is defined like this really,

T(n)= 3 * T(n/2) + [n * log(n)] : n=2,4,8,16...

Now this is equivalent to this relation S,

S(k) = 3 * S(k-1) + [2^k * log(2^k)] : k=1,2,3,4...

with the variables related as n = 2^k.

When the recursion evaluates, S goes like S(1), S(2), S(3).... whereas T goes like T(2), T(4), T(8) ... but they both produce the exact same sequence. This can be checked if a starting value is defined, like say S(0) = T(1) = 1 for example. The next step then becomes,

T(2) = 3*T(2/2) + [2 * log(2)] = 3 + 2*log(2)
S(1) = 3*S(1-1) + 2^1 * log(2^1) = 3 +2*log(2)

and then

T(4) = 3*T(4/2) + 4*log(4) = 3*(3 + 2*log(2)) + 4*log(4)
S(2) = 3*S(2-1) + 2^2 * log(2^2) = 3*(3 + 2*log(2)) + 4*log(4)

etcetera.

The situation now is that S can be solved instead of T because they're equivalent. I don't know if S is any easier but at least it's a regular difference equation so a more standard solving apparatus will be available.

[superbonzo]

It's not that hard.

well, yes, that's straightforward being a mere substitution of variable; the tricky part I referred to in my post is the method I used to solve that difference equation:


... then the tricky part: the matrix is not diagonalizable, so you should find a continuous curve passing from the matrix that is diagolizable in an open subset of its domain containing the preimage of the matrix, then diagolize, take the nth power, take the limit and return back to the original equation.


anyway, as I said in the EDIT, there is an easier and more direct way ( that I didn't post being in wait of an OP's attempt ... ).

[nuzzle]

well, yes, that's straightforward being a mere substitution of variable; the tricky part I referred to in my post is the method I used to solve that difference equation:


Well, I thought that once the recurrence equation was transformed into an equivalent standard difference equation the solution would be fairly straightforward, but I haven't actually tried so I may be wrong.

[nuzzle]

I tried to solve the S difference equation,

S(k) = 3 * S(k-1) + [2^k * log(2^k)] : k=1,2,3,4...

and got this explicit solution. I made a variable change but k is basically n.

S(n) = 3^n * [1 + 1/log2(B) * [6 - [(2/3)^n * (6 + 2*n)]]]

To check the explicit solution one can generate a few numbers using the difference equation. B is the actual base of the log function. If one for simplicity sets B=2 then the difference equation becomes,

S(k) = 3 * S(k-1) + [2^k * k] : k=1,2,3,4...

The startvalue that has been used is S(0) = 1. Then follows recursively,

S(1) = 3 * S(0) + 2^1 * 1 = 3*1 + 2*1 = 5
S(2) = 3 * S(1) + 2^2 * 2 = 3*5 + 4*2 = 15 + 8 = 23
S(3) = 3 * S(2) + 2^3 * 3 = 3*23 + 8*3 = 69 + 24 = 93

If one instead uses the explicit solution one gets,

S(1) = 3^1 * [1 + [6 - [(2/3)^1 * (6 + 2*1)]]] = 3 * [1 + 6 - [(2/3) * 8]] = 3 + 18 - 16 = 5
S(2) = 3^2 * [1 + [6 - [(2/3)^2 * (6 + 2*2)]]] = 9 * [1 + 6 - [(4/9) * 10]] = 9 + 54 - 40 = 23
S(3) = 3^3 * [1 + [6 - [(2/3)^3 * (6 + 2*3)]]] = 27 *[1 + 6 - [(8/27) * 12] = 27 + 162 - 96 = 93

Well, so far so good. It looks like the explicit solution is correct indeed.

The most efficient way probably would've been to use the z-transform but I learned in a textbook that difference equations of the S form has a standard solution which I used. I plugged in the specific details of S and after some algebraic juggling I arrived at the solution presented here.

[superbonzo]

The most efficient way probably would've been to use the z-transform ...

using the z-transform with a log term can be error prone ( at least for me :) ) because you can easily get the wrong branching of the power series, so I preferred avoiding it ...

IMHO, a more systematic way ( after a standard solution, of course ) is to linearize the equation as I suggested in post #2, and solve it through a "nearly" standard diagonalization procedure.

anyway, the "ansatz" method ( again, see post #2 ) seems the easiest:

given that T(n) goes as n^( log(3) /log(2) ) and that (n/2)log(n/2) equals a linear combination of n and nlogn we make the trivial ansatz

T(n) = A n^a + B n + C n log(n), where I set a := log(3) /log(2) for brevity

then

T(n) - 3 T(n/2) = A n^a + B n + C n log(n) - 3 A n^a / 2^a - 3 B/2 n - 3 C/2 n log(n) - 3 C log(2)/2 n
= ( -B/2 - 3 C log(2)/2 ) n - C/2 n log(n)

equating the RHS to the RHS of the original equation, we have

-B/2 - 3 C log(2)/2 = 0
-C/2 = 1

therefore

T(n) = A n^a - 6 log(2) n - 2 n log(n)

and finally, setting T(1) = A - 6 Log[2]

T(n) = ( T(1) + 6 log(2) ) ) n^( log(3)/log(2) ) - 6 log(2) n - 2 n log(n)

[nuzzle]

anyway, the "ansatz" method ( again, see post #2 ) seems the easiest:


Yes it does and one doesn't first have to produce a difference equation as I did.