1. Good post? |

## Algorithms Query

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

Can someone explain!!!

2. Good post? |
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.

3. Good post? |
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]

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

SEO by vBSEO ©2010, Crawlability, Inc.