Algorithms Query

[rahul_badboy]

i am getting the option a as the answer,but the correct answer is option d.

Can someone explain!!!


Thnks in advance

[MagicTest2008!!!]

Hi,

This problem can not be solved with Master Theorem, since it doesn't
belong to any of the three cases(I guess you
obtain (A) with Master Theorem).

My way is to build a recursion tree:

log(N)--------------------- log(N)
log(N/2) log(N/2)-------- log(N)-2log2
log(N/4) log(N/4) log(n/4) log(N/4)-- log(N)-4log4
............

log(1) log(1) ... log(1)--------- log(N)*T(1)

----------------------------------------------------------
total: O(log(N)*log(N))

Hope it helps.

[dhruvbird]

You can use the Master Theorem on wikipedia Master theorem - Wikipedia, the free encyclopedia to get the formula (case-2 is different from that in CLRS).

So, you have:
if f(n) == n ^ log(base-b)(a) . (log n)^k (k >= 0) then:
F(n) = (log n)^(k+1)

According to that formula, you have: F(n) = (log n)^2

[Thanks to nomind for this]