retagged by
4,377 views

4 Answers

Best answer
3 votes
3 votes

T(n) = 100 T($\frac{n}{99}$) + log(n!)

it can be written as 

T(n) = 100T($\frac{n}{99}$) + nlog(n)

Applying Master's Theorem

a = 100 , b = 99

$n^{\log_{99}100}$

 $n^{\log_{99}100}\approx n$

Now, 

n < nlog(n)

So,

T(n) = Θ(nlog(n))

selected by
1 votes
1 votes

n ! is approximately equals to n^n.

Hence, log( n !) = log(n^n) = n logn

Now, Recurrence Relation will be:

T(n) = 100 T (n/99) + nlog(n) 

Comparing with General Recurrence Relation:

T(n) = a T( n / b) + n^k.log^(p)n

a =100 , b = 99 , k = 1 , p = 1 

a  >  b^k

So, O(n^log 100 base 99)

log 100 base 99 is approximate equals to 1.

Hence, O(n).

Plz make me correct if i m wrong...

1 votes
1 votes
we can apply here master theorem

t(n)=aT(n/b)+nlogn

i.e here logn! expand s nlogn

a=100

b=99

k=1

p=1

b^k=99^1=99

i.e. a>b^k   , 100>99

hence case 1:

is applied O(n^log100base99)    from= O(n^log a base b)

hence time complexity is T(n)=O(n)
0 votes
0 votes
We can find the answer for this recurrence relation but the given answer is not justified...

I have seen the explanation given above.. But one thing we must understand everytime we are comparing n and nlogn which is contradiction as master theorem says one can be compared only if it is polynomial time greater or smaller.. Therefore answer is not justified.
Answer:

Related questions