ansaurus

Question

Answer 1

A:

The difference bettween 3.5 and 3.6 is the ceil and floor functions in T(n/4). Other than that they are identical. And as far as i can tell the difference does not matter to the calculations for O(T(n)) as you can see from the expected results.

I hope this helps.

Robert Massaioli 2009-10-18 22:29:46

I don't think it helps. Notice that the text in 3.6 claims that the exercise is difficult, so something must matter here.

Martin v. Löwis 2009-10-18 22:32:44

The difference will, presumably, be in showing how fast the series converges. But aside from that the attack should be the same.

dmckee 2009-10-18 22:44:09

@dmckee: O(n log n) is not about convergence whatsoever. For example, sin(x) is in O(1), yet sin will never converge.

Martin v. Löwis 2009-10-18 22:46:55

Sorry wrong word. I should have said terminates. The recurence relation generates a series. A terminating series. How fast the series terminates depends on the choice of floor or ceiling, and you have to show how the termnation is bounded to finish the problem.

dmckee 2009-10-19 01:31:33

Answer 2

+9 A:

If you're a bit more careful in your solution to 3.5, the difference will be a bit clearer. Your first line

T(n) <= n/4 (lg n)/4 + 3n/4 (3 lg n)/4 + n

isn't quite right. First of all, the inductive assumption is that there is a constant C such that

T(n) <= C n log n

so you probably should keep that C around. Second, you're skipping the step where you remove the floor function. What you really know is (ignoring the constant C for simplicity) is

T(n) <= floor(n/4) lg (floor(n/4)) + floor(3n/4) lg (floor(3n/4)) + n

So how do you take care of the floor? Well, floor(x) <= x; but what about lg(floor(x)) (which shows up twice)? The key here is that lg is an increasing function, so lg(floor(x)) <= lg(x) also. So

T(n) <= n/4 lg(n/4) + 3n/4 lg(3n/4) + n

Now clean it up with some properties of logarithms (you will need to use that hint about lg 3) and finish your inductive step.

OK, so knowing that, what's the difference with 3.6? Well, now you have the ceiling function instead of the floor function, so you can't just ignore it. But

ceiling(x) <= x + 1

so you can work similarly, with some extra + 1 factors lying around. Try to use their hints, and it should be fine.

Jesse Beder 2009-10-18 22:40:29

Good answer. This is as much support as we can give.

Martin v. Löwis 2009-10-18 22:45:34

Thanks. I was trying to show the key points but leave the details for the poster. If you feel like I should give more or less detail, please let me know.

Jesse Beder 2009-10-18 22:50:50

ansaurus

tags:

views:

answers:

Big-O algorithm analysis

related questions