Take the 2-minute tour ×

There's a problem in "Introduction to Algorithms" that says: (4.4-6)

Argue that the solution to the recurrence T(n) = T(n/3) + T(2*n/3) + cn
where c is a constant is Ω(n log2n) by appealing to a recursion tree.

I use a recursion tree and at last I get T(N) >= n log3n.
I don't know the next step to show that T(N) >= n log2n,
I also Googled it and somehow I feel something is wrong with the answers, because they say when T(N) >= n log3n then T(N) >= n log2n (but log3n is not greater than log2n).

share|improve this question
how did you deduce that log_3(n) > log_2(n)? plot these two functions and you'll see that log_3(n) is always less than log_2(n) that's obvious. –  Cena Pi Jul 4 '13 at 10:17
please someone help me! –  Cena Pi Jul 4 '13 at 10:29
Sorry, my mistake, it's the other way round. You're right. log_3(n) < log_2(n). That's what you get for typing stuff before writing it on paper... –  Carsten Jul 4 '13 at 10:46
so can you help me? –  Cena Pi Jul 4 '13 at 10:47

2 Answers 2

up vote 1 down vote accepted

In asymptotic bounds, the base of the logarithm doesn't matter since it's only a constant variation.This is due to the change of base in logarithm.

loga x= logb x/logb a

This is why people don't write base in asymptotic bounds.

share|improve this answer

Recall the definition of big omega: f(n) is in Omega(g(n)), if f is bounded below by g asymptotically. Or, if you like it more mathy:

definition of Big Omega

Let's define f(n) = n * log_3(n) and g(n) = n * log_2(n).

Now, if we can find a constant c so that f(n) > c * g(n), then we have shown that f(n) is in Omega(g(n)).

    log_3(n) = log_2(n) / log_2(3)
    log_2(3) ~= 1.585 < 2
=>  log_3(n) > 2 * log_2(n)
=>  n * log_3(n) > 2 * n * log_2(n)
=>  f(n) > c * g(n)

for our chosen value of c = 2 (you can, of course, choose any other value, as long as c > log_2(3).

share|improve this answer

Your Answer


