solving recurrence

Question

1.00/5 (2 votes)

See more:

olve the following recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1):
T(N) = N + T(N-3)

I've done the solving i just can't find the pattern.

step 0) N+ T(N-3)
step 1) 2N-3+T(N-6)
step2) 3N -9+T(N-9)
step3) 4N-18 +T(N-12)
step4) 5N-30 +T(N-15)
step) 6N-45+T(N-18) .... and so on. I have to find a pattern, an equation that works for every value for k.

Posted 30-Jan-11 14:31pm

bowww

Add a Solution

Comments

Sergey Alexandrovich Kryukov 30-Jan-11 20:33pm

Is it a homework assignment problem? We're not interested to solve them. However, if you move in right direction and get stuck, you might hope for someone's help. Please...
--SA

Nithin Sundar 30-Jan-11 23:43pm

Do the math, form a logic and put it into your code. When you get stuck, show us what you have done and we'll guide you.

bowww 31-Jan-11 8:53am

I tried and I can't find a pattern that satisfies the second number 0,3,9,18,30,45... i Know it moves likes this ..3X1=3, adding 2 to the 1 ..3X3=9, adding 3 to the 3 gives you 3X6=18, adding 4 to the 6 gives u 3X10=30, adding 5 to the 10 3x15=45 ..my problem is that i cant find a general equation that satisfies all of the above.. i cant put it into an equation.

Sandeep Mewara 31-Jan-11 0:59am

I am not clear on what exactly you are looking for. You said you solved it and yet you seek a pattern. How come you solved without pattern. Surely I am missing something. Can you elaborate on what you are trying to do here and where are you stuck?

bowww 31-Jan-11 8:50am

ok I need to find a general equation that works for every value of k (0,1,2,3) and satisfies the pattern. as you can see the first Number increases by 1 the second number 1,3,9,18,30,45 is the part where i can't find an expression that satisfies it .. T(N-3),T(N-6),T(N-12)..increases by 3 each time.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sandeep Mewara · Accepted Answer · 2011-01-31T04:09:00

Solution 2

the second number 1,3,9,18,30,45 is the part where i can't find an expression that satisfies it
First of all, it's:
0, 3, 9, 18, 30, 45...

Now, the series is: Difference is increasing by amount 3...

Series: 0, 3, 9, 18, 30, 45...
Diff: 3(3-0), 6(9-3), 9(18-9), 12(30-18), 15(45-30)....

I guess, now, this should be enough for you, to get this series equation. :)

UPDATE:
Here you go, the link that will explain how I got that: same series that I told you[^]

Posted 31-Jan-11 4:09am

Sandeep Mewara

Updated 31-Jan-11 6:17am

v3

Comments

bowww 31-Jan-11 11:59am

I know it is 0,3,9,18.. i just mistyped the 1.. i still don't get what you are doing here, i tried understanding your method but cant seem to get it :S

Sandeep Mewara 31-Jan-11 12:00pm

It's 3,6,9,12,15... a simple AP series when you take the difference of 1st-2nd, 2nd-3rd, 3rd-4th, 4th-5th...

bowww 31-Jan-11 12:04pm

i get that it is the difference of 1st-2nd, 2nd-3rd, 3rd-4th, 4th-5th...but in order for me to make an equation for that I will only satisfy the first step .. im so confused.

Sandeep Mewara 31-Jan-11 12:08pm

It's basic class 12 maths.

Expression is: (3n + 3n^2)/2

You can get it yourself or you want me to explain how I got this?

bowww 31-Jan-11 12:06pm

my series is 0,3,9,18,30 ...so 3X0=0,3X1=3,3X3=9, 3x6=18 adding to the previosu value 1,2,3,4,5,6

Sandeep Mewara 31-Jan-11 12:18pm

Updated the answer with the link that will explain you all.

bowww 31-Jan-11 12:37pm

i understand it but I can never know how to get those equations. I tried so many different ones but never got to this one. If you could explain that would be great:) thanks a lot for your help

Sandeep Mewara 31-Jan-11 12:38pm

The link I shared has exaclty the steps I take/took. Have a look at that and you too can try then.

bowww 31-Jan-11 12:39pm

ok thanks :) I really appreciate your help :)

Sandeep Mewara 31-Jan-11 12:41pm

My pleasure!

Sandeep Mewara 1-Feb-11 0:53am

Close the question that would help others too in future for something same.