edited by
1,897 views

2 Answers

Best answer
2 votes
2 votes

MASTER'S THEOREM :

Let f be an increasing function that satisfies the recurrence relation
f(n) = af(n/b) + cnd
whenever n = bk, where k is a positive integer, a ≥ 1, b is an integer greater than 1, and c
and d are real numbers with c positive and d nonnegative. Then f(n) is:

1) O(nd ) if a < bd ,
2) O(nd log n) if a = bd ,
3) O(nlogb a) if a > bd
.

now for given question, comparing  by standard form, gives c = logn (a function of n) while according to the theoram it should be a constant value...

So we cannot apply the Master's Theoram in the given question...

selected by

Related questions

3 votes
3 votes
0 answers
1
Sona Barman asked Jan 8, 2018
2,306 views
I have doubt regarding Master theorem.In which situation we should use Normal Master theorem/extended Master theorem?
1 votes
1 votes
1 answer
2
2 votes
2 votes
1 answer
3
iarnav asked Jan 11, 2018
1,015 views
can we solve this T(n) = T(n/2) + 1 using master theorem?
1 votes
1 votes
1 answer
4
dragonball asked Dec 19, 2017
547 views
T(n) = 2T(n/2) + nlogna. O(nlogn)b.n(log^2n)c.O(n^2)