Could someone help me with these questions please.

I really don't know where to start.

Thank you.

1) T(n)=7T(n-4)+n

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

Printable View

- Feb 24th 2014, 04:51 PMMelody2T(n) questions
Could someone help me with these questions please.

I really don't know where to start.

Thank you.

1) T(n)=7T(n-4)+n

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

- Feb 24th 2014, 07:19 PMProve ItRe: T(n) questions
There are not any questions posted here, only equations. What are you trying to do with these equations?

- Feb 24th 2014, 07:50 PMMelody2Re: T(n) questions
Thank you Prove It.

I really have no idea. I was actually wondering if i even had a question. Thanks for clearing that up.

Maybe they were intended as simultaneous equations. I really don't know.

Regards,

Melody. - Feb 25th 2014, 03:35 AMBobPRe: T(n) questions
Hi Melody

I suspect that these are difference equations.

Take the first one for example, $\displaystyle T(n)=7T(n-4)+n.$

That would imply that $\displaystyle T(4)=7T(0)+4, \quad T(5)=7T(1)+5, \quad T(6)=7T(2)+6$ and so on.

The object of the exercise is to find an expression for $\displaystyle T(n).$

The general solution of the equation is quite messy (and I would guess that it is not what is required), but the particular solution is relatively easy to find.

Assume that $\displaystyle T(n)=An + B$ for some constants $\displaystyle A \text{ and } B$ and substitute into the difference equation, treating it as an identity.

Solve, and you should find that $\displaystyle T(n)=-\frac{n}{6}-\frac{7}{9}=\text{ (for convenience )}-\frac{3n}{18}-\frac{14}{18}.$

So,

$\displaystyle T(0)=-14/18, \quad T(1)=-17/18, \quad T(2)=-20/18, \quad T(3)=-23/18,$

$\displaystyle T(4)=-26/18, \quad T(5)=-29/18, \quad T(6)=-32/18$

and so on.

Check to see that these satisfy the three example equations I gave earlier.

Try your luck with the second one, I've not attempted it yet. - Feb 25th 2014, 05:37 PMMelody2Re: T(n) questions
Why would i assume the above line and how would that lead to the below line? (Thinking)

Thanks BobP,

I have include a question inside - I can't get this multi quote thing to work. I separated the two bits myself.

Please can someone tell me what the trick is to using multi quote (Headbang) - Feb 26th 2014, 01:17 AMBobPRe: T(n) questions
The method I used is known as a 'trial solution method', and it is just that. You try something, if it works fine, if not try something else. With practice it's usually possible to guess what the solution looks like.

Have you done any work on second order ODE's with constant coefficients ? That's where your most likely to come across it. It's a commonly taught method for finding the Particular Integral. The general solution of such an equation will consist of the Particular Integral plus a Complementary Function (which is the solution of the corresponding homogeneous equation and which will contain two arbitrary constants). It's pretty much the same for the difference equation we are discussing, its general solution consists of two parts, a Particular Solution (which is what I've found), plus the solution of the corresponding homogeneous equation, (which I haven't).

For the equation $\displaystyle T(n)=7T(n-4)+n,$ we 'guess' that the solution is of the form $\displaystyle T(n)=An+B$ where $\displaystyle A \text{ and } B$ are constants, to be calculated.

Substitution into the equation gets us $\displaystyle An+B=7\{A(n-4)+B\}+n,$

and on rearranging, $\displaystyle -6An+28A-6B=n.$

This is to be considered as an identity, that is, it has to be true for all values of $\displaystyle n.$

That implies that $\displaystyle A=-1/6 \text{ and }B=-7/9,$ (the part without the $\displaystyle n$ in it must equal zero).

In answer to your other question, I struggle with one quote let alone two or more.