Click here to Skip to main content
14,447,082 members
Rate this:
Please Sign up or sign in to vote.
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
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

Rate this:
Please Sign up or sign in to vote.

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[^]
   
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.

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100