Algorithms - Recursive Relations

[astudent1929]

Given:
For n = 1, T(1) = 1
For n > 1, T(n) = 7 T(n/2) + n^2

Find the closed form of the recurrence relation via the substitution method.

I have tried to substitute n/2, n/4, n/8, etc. but I can't intuitively find the relation from seeing the iterations.

 

[JeffM]

It’s late, and I am sleepy. I seem to be missing something.

If n = 3, what is is [MATH]T \left ( \dfrac{3}{2} \right )?[/MATH]
Please accept my apologies if I am simply being dim.

 

[astudent1929]

From my understanding of the given info, I think that n must be an even number for n>1.
But I am not really sure how to go from there.

 

[JeffM]

Assuming the source is English, please provide the “info given” exactly and completely.

 

[astudent1929]

I posted exactly the info that was given. There was nothing else provided. I was only making the assumption that n must be an even number for n > 1.
But after plugging in the recurrence equation into wolfram alpha, they gave the solution T(n) = [MATH] \frac{1}{3}*(4n^2-1)[/MATH].
I am not sure how they derived the solution, but I am trying to figure out the process.

 

[skeeter]

Given:
For n = 1, T(1) = 1
For n > 1, T(n) = 7 T(n/2) + n^2

note the recurrence relation you posted evaluated for n = 2 ...

[MATH]T(2) = 7 \cdot T\left(\frac{2}{2}\right) + 2^2 = 7 \cdot T(1) + 4 = 7 \cdot 1 + 4 = 11[/MATH]
for the formula you claim Wolfram came up with ...

[MATH]T(2) = \frac{1}{3}(4 \cdot 2^2 -1) = \frac{1}{3}(15) = 5[/MATH]
Either the original recurrence relation you posted is incorrect, or Wolfram is ... ?

 

[skeeter]

maybe the recurrence relation was

[MATH]T(n) = T\left(\frac{n}{2}\right) + n^2[/MATH] with no 7 ?

 

[Dr.Peterson]

Given:
For n = 1, T(1) = 1
For n > 1, T(n) = 7 T(n/2) + n^2

Find the closed form of the recurrence relation via the substitution method.

I have tried to substitute n/2, n/4, n/8, etc. but I can't intuitively find the relation from seeing the iterations.

Can you show us what "the substitution method" is, as taught to you? Do you have an example?

As I see it, the recurrence inherently applies only to n = 2^k, as it tells us what happens each time n is doubled.

Searching for the method, I found this page that indicates alternative names for it, and gives an example very much like yours.

 

[astudent1929]

note the recurrence relation you posted evaluated for n = 2 ...

[MATH]T(2) = 7 \cdot T\left(\frac{2}{2}\right) + 2^2 = 7 \cdot T(1) + 4 = 7 \cdot 1 + 4 = 11[/MATH]
for the formula you claim Wolfram came up with ...

[MATH]T(2) = \frac{1}{3}(4 \cdot 2^2 -1) = \frac{1}{3}(15) = 5[/MATH]
Either the original recurrence relation you posted is incorrect, or Wolfram is ... ?

My bad. I double-checked what I entered into wolfram, and it was the wrong equation. What I posted here is indeed the correct equation. Please disregard what I wrote about wolfram.

Can you show us what "the substitution method" is, as taught to you? Do you have an example?

As I see it, the recurrence inherently applies only to n = 2^k, as it tells us what happens each time n is doubled.

Searching for the method, I found this page that indicates alternative names for it, and gives an example very much like yours.

Yes, the page that you are showing is precisely the substitution method. I substituted n/2, n/4, n/8 etc. to iteratively find the solution, but it was difficult for me to construct the iterations into a fitting solution.

 

[Dr.Peterson]

Do you have any examples more like your problem (that is, with a term other than a constant like their 2)? And can you show your actual work, so we can see if there is an actual error?

I tried doing what I think they are saying, and it got more complicated than I wanted it to be. But I don't have as much to go on as you. I've never studied this topic, and you have.

Finally, what did you enter into WA?

 

[Cubist]

Using the info in the link that @Dr.Peterson found in post #8, I think I followed the same method but I took some shortcuts (because their work was very verbose). This is what I got so far...

Just plugging different values into the original recurrence relation...

T(n/2) = 7*T(n/4) + (n/2)^2   eqn A
T(n/4) = 7*T(n/8) + (n/4)^2   eqn B
T(n/8) = ????                 eqn C

--

k=2 : T(n) = 7*T(n/2) + n^2                  original
           = 7*(7*T(n/4) + (n/2)^2) + n^2    using A
           = 7^2*T(n/4) + 7*(n/2)^2 + n^2

k=3 : T(n) = 7^2*T(n/4) + 7*(n/2)^2 + n^2    copy the line above
           = 7^2*( 7*T(n/8) + (n/4)^2 ) + 7*(n/2)^2 + n^2    using B
           = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2
           = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2

k=4 : T(n) = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2  copy the line above
           = ???? (hint use eqn C)

OP, can you verify the above work, and if it's correct then work out the two ????
Note: I recommend you don't rewrite 7^2 as 49 (etc). Doing this will make spotting a pattern much simpler!

 

[astudent1929]

Using the info in the link that @Dr.Peterson found in post #8, I think I followed the same method but I took some shortcuts (because their work was very verbose). This is what I got so far...

Just plugging different values into the original recurrence relation...

T(n/2) = 7*T(n/4) + (n/2)^2   eqn A
T(n/4) = 7*T(n/8) + (n/4)^2   eqn B
T(n/8) = ????                 eqn C

--

k=2 : T(n) = 7*T(n/2) + n^2                  original
           = 7*(7*T(n/4) + (n/2)^2) + n^2    using A
           = 7^2*T(n/4) + 7*(n/2)^2 + n^2

k=3 : T(n) = 7^2*T(n/4) + 7*(n/2)^2 + n^2    copy the line above
           = 7^2*( 7*T(n/8) + (n/4)^2 ) + 7*(n/2)^2 + n^2    using B
           = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2
           = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2

k=4 : T(n) = 7^3*T(n/8) + 7^2*(n/4)^2 + 7*(n/2)^2 + n^2  copy the line above
           = ???? (hint use eqn C)

OP, can you verify the above work, and if it's correct then work out the two ????
Note: I recommend you don't rewrite 7^2 as 49 (etc). Doing this will make spotting a pattern much simpler!

Yes, what you have posted is what I got up to. It is all correct. But after that part, the next step is to see the pattern and convert it into a closed formula, and that's where I have difficulty. I am really lost on how the closed-form should look like.

 

[astudent1929]

Do you have any examples more like your problem (that is, with a term other than a constant like their 2)? And can you show your actual work, so we can see if there is an actual error?

I tried doing what I think they are saying, and it got more complicated than I wanted it to be. But I don't have as much to go on as you. I've never studied this topic, and you have.

Finally, what did you enter into WA?

I entered T(n) = T(n/2) + n^2 into Wolfram Alpha's calculator. (Here is a link of it : LINK)
I forgot that there was a constant in front of T(n/2).

 

[Dr.Peterson]

I entered T(n) = T(n/2) + n^2 into Wolfram Alpha's calculator. (Here is a link of it : LINK)
I forgot that there was a constant in front of T(n/2).

But what you entered is entirely different: g(n+1)=n^2+g(n).

If you enter g(n)=n^2+7g(n/2), you get something like what I got, which I considered too ugly to consider likely for an exercise.

 

[Cubist]

Yes, what you have posted is what I got up to.

Please post your work next time so that we know exactly where you're stuck.

But after that part, the next step is to see the pattern and convert it into a closed formula, and that's where I have difficulty.

To be clear, are you stuck on...

• seeing the pattern
• OR converting the pattern into a closed formula