Big-O algorithm analysis

Question

The questions: alt text http://img12.imageshack.us/img12/2706/image2ot.jpg

What I've done: alt text http://img29.imageshack.us/img29/9192/image3sc.jpg

But I've got totally no idea the difference between 3.5 and 3.6.

Answer 1

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.