Our new Indie Games subforum is now open for business in G&T. Go and check it out, you might land a code for a free game. If you're developing an indie game and want to post about it, follow these directions. If you don't, he'll break your legs! Hahaha! Seriously though.
Our rules have been updated and given their own forum. Go and look at them! They are nice, and there may be new ones that you didn't know about! Hooray for rules! Hooray for The System! Hooray for Conforming!

# Computer Algorithms help

Registered User regular
I don't get them, I've been jamming myself full of caffeine for every class, reading the book, and looking up supplemental stuff online and it is still a byzantine mess to me. Unfortunately, there is now an assignment due this week and poking at it for hours has ended with pages and pages of scribbles that don't make a lot of sense. Anyone good at explaining this that can help?

Here's an example: "Solve the following recurrences. If you cannot find an exact answer, give the best upper and lower bounds that you can."

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

Poking around gets me a big equation with b's, a's, and j's which I can't figure out how to apply because I'm not given T(1).

As far as I can understand it, it seems like n^3 gets smaller with each recursion, and so does 3T(n/2)? So it seems like the lower limit should be something like 3/2 + 1 or 2.5, and the upper limit should be uh...3n?

I've got a list of these to do for the homework and feel like I'm just spinning in circles, can anyone point me in the right direction here? I'm not even sure of what a solution should look like at this point, if I've already gotten there, or if I've totally missed. Argh!

Edit: I am planning on going to the teacher's office hours, but I'd really like to have something vaguely in the right direction instead of stumbling in all bleary eyed and waving my arms helplessly.

Hypatia on

## Posts

• Registered User regular
If your course has covered the Master theorem, that's the way to go.

• Registered User regular
Hey Hypatia! Eek, that's some crazy stuff... I'm trying to read up on it and catch up, I want to be of help...

Okay, so I found this:

http://www.cs.ucr.edu/~jiang/cs141/recur-tut.txt

Which appears to be a wealth of knowledge on how to solve these problems... though my extremely un-leet math skills meant that I could only get so far. It looks like their technique is to continually replace T with the (n - X) version of the equation, where X is the number of times you've done that replacement... and you keep doing that until you find a pattern that lets you simplify the equation.

Here's what I got so far based on that:

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

... (Now replace for T(n-1))

T(n) = 3[3T((n-1) / 2) + (n-1)^3] + n^3

... (one more, this time n - 2)

T(n) = 3[3[3T((n-2) / 2) + (n-2)^3] + (n-1)^3] + n^3

... (Let's try to simplify)

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

... (Okay, we can see some patterns that emerge as the number of substitutions equals n, whatever n may be... let's take a look and try to identify these patterns so we can extrapolate to the nth iteration: for example, with each iteration the original 3 *... at the start of the formula becomes more like 3 * X, where X is the current iteration, so we can extrapolate that to 3 * n when the number of substitutions that have taken place becomes n... follow that logic down the line.)

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

(The "..." above indicates ~n numbers of additional factors... but they continue in the manner seen above, with the "3n" portion eventually dwindling from 3n down to just 3, and the "n^3" portion increasing from (n - (n - 2))^3 to (n - (n - n))^3 or just n^3)

(From here, we can see that the first one evaluates to 0 because n-n / 2 will = 0, so 3n doesn't matter...)

T(n) = 0 + (3(n -1))(n-n)^3 + (3(n - 2))(n - (n - 2))^3 + ... + 3(n - (n - n))^3 + n^3

(And the same with the second (n-n)^3 = 0...)

T(n) = 0 + 0 + (3(n - 2))(n - (n - 2))^3 + ... + 3(n - (n - n))^3 + n^3

(So now what we're left with is something that my math skills can't resolve... but you can definitely see a pattern in it. The "3n" portion of the formula is gradually decreasing while the "n" portion is increasing... I get the feeling that you have better math skills than I, perhaps you know of a trick that would simplify this situation?)

I hope this has been helpful... I'm a bit glossed over by sickness, but I wanted to try and help. Hopefully this did provide some help: I wish my math skills were better. =( Check out that linked text file, it really helps I think.

EDIT: I'm definitely feeling addled... if this isn't helpful, please disregard. My math skills are really rusty, but when I saw that linked article I felt like it made a lot of sense... but when I got to the point above I was stopped.

EDIT 2: That text file mentions something called the "arithmetic progression formula" to resolve the "+ ... +" section, which may possibly apply here... it does look like it progresses similarly to their example at least... hopefully that helps)

EDIT 3: Can someone with real math skill jump in and help? =) I think the approach in the linked text file is correct... but I'm a bit worried that I either screwed something up or made it worse. A double-check by someone with good math skills, and perhaps someone who can show how you'd finish this off (or if I'm going in absolutely the wrong direction, pointing that out), would be wonderful.

EDIT 4: Ooh, more on master theorem here if it helps, from what was posted above by Clipse!

http://www.cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf

It sounds like it can't be used to actually "solve" the relation according to the notes above, so you might want to double check before you use it.

\$14,276 for Child's Play from the Cookie Brigade at PAX Prime 2011!!!
• Registered User
So... you can't really eyeball these like you did unless you're allowed to apply the master theorem.

If you need to solve them by hand, the first thing you should do is repeated substitution.

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

we know that T(n/2) is defined as: 3*T(n/4) + (n/2)^3 by just substituting n/2 into the equation

Thus:
T(n) = 3 * (3 * T(n/4) + (n/2)^3) + n^3
= 9*T(n/4) + (3*(n/2)^3 + n^3)

Then we substitute for T(n/4):
T(n/4) = 3*T(n/8) + (n/4)^3

T(n) = 9*(3*T(n/8) + (n/4)^3) + (3*(n/2)^3 + n^3)
= 27*T(n/8) + (9*(n/4)^3 + 3*(n/2)^3 + n^3)

seeing a pattern yet?

the term with T in it is (3^x) * T(n/2^x) where x is the number of substitutions. It starts out as x=0, the original equation, and is T(n). We substitute once and get 3*T(n/2), again and we get 9*T(n/4), 27*T(n/8), etc.

With me so far?

The second part is a sum, and each term is 3^x * (n/(2^x))^3. So the first term is 1 * n^3, or n^3. The next term is 3*(n/2)^3, etc.

Ok, so now if I tell you how many substitutions you need to make, you can write out the formula for me. The only question left is: how many substitutions do you need to make?

Well, we keep substituting until we hit a base case, usually something like n=1. How many steps will it be until we hit this case (hint: we keep dividing by 2 over and over again until we hit 1...)

Once you've worked this out, the only other step is to prove that your substitution guess is actually correct. This is almost always done by induction, and you should be able to grab that through your class notes.

• Registered User
Also, no offense, but ignore VThornheart because he's using the wrong formula (T(n-2) instead of T(n/2)).

• Registered User regular
No worries! I'm glad you came along... I was trying to help, but was a bit over my head. Seeing those notes, it was clear that substitution was the way to go... but I had a feeling that I was not doing it correctly. =(

\$14,276 for Child's Play from the Cookie Brigade at PAX Prime 2011!!!