1

This is possibly a duplicate, but I couldn't find the answer to it.

For example, if we have $lg(n!) = \theta ({n lg n})$, then can we sustitute $n$ with any other function? Like putting $n=n!$ will make it:

$lg((n!)!) = \theta ({(n!) lg (n!)})$. If its true, then can we replace $n$ with any other function? Some reasoning in simple words will be highly appreciated.

shiva
  • 492
  • Writing $n$ or $f(n)$ is immaterial, these are just numbers and you study the behavior for increasing values. –  Mar 06 '18 at 08:45

1 Answers1

0

By definition, $\log(n!) = \Theta(n\log n)$ means exists positive constants $k,K$ s.t. for $n$ large enough $$kn!\le n\log n\le Kn!.$$ If $f(n)\to\infty$ when $n\to\infty$ then $$k f(n)!\le f(n)\log f(n)\le K f(n)!$$ also will be true for $n$ large enough.

Martín-Blas Pérez Pinilla
  • 41,546
  • 4
  • 46
  • 89