Clever Geek Handbook

Big-O Algorithm Analysis

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

What I did: alt text http://img29.imageshack.us/img29/9192/image3sc.jpg

But I have no idea about the difference between 3.5 and 3.6.

+2


source to share


2 answers


If you are a little more careful with your 3.5 solution, the difference will be a little clearer. Your first line

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

not entirely true. First of all, the inductive assumption is that there is a constant C

such that

T(n) <= C n log n

so you should probably support that C

. Secondly, you skip the step where you remove the floor function. What you really know (disregarding 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 sex? Well floor(x) <= x

; but what about lg(floor(x))

(which appears twice)? The key here is what lg

is an incremental function, therefore lg(floor(x)) <= lg(x)

. So

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

Now clear it up with some log properties (you will need to use this hint lg 3

) and complete your inductive step.

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

ceiling(x) <= x + 1

so that you can work the same way with some additional factors + 1

lying around. Try using their clues and you should be fine.

+10


source


The difference between 3.5 and 3.6 is the ceil and floor functions in T (n / 4). Moreover, they are identical. And as far as I can tell, the difference is not computationally significant for O (T (n)), as you can see from the expected results.



Hope this helps.

-1


source






More articles:


All Articles