solve the recurrence using any method just solve it

Question

T(n) = 100 T (n/99) + log(n!) 

Answer is T(n) = θ (n log n)

a)answer is justified

b)answer is not justified

c)cannot be determined

d)none

Answer 1

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))

Comments

You can write n as O(nlogn) but you should not write theta(nlogn). theta(nlogn) means both worst case and best case which will not be correct here.

Answer 2

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...

Comments

sir answer is :

θ ( n log n )

---

somebody please tell how to solve it

---

@ akash.dinkar

I am also solving the same way. I also think this is the correct approach

Answer 3

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)

Answer 4

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.

Comments

But, here comparison is polynomial times smaller. In the comparison, the first term is approximately equal to n and second term is nlogn.

random example : sqrt(n) and nlogn comparable.

So, here also they must be comparable.