Skip to main content
added 53 characters in body
Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$

Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.

This is tight because $\Omega(n \log n)$ is also a lower bound since: $$ T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n). $$

To summarize, you have $T(n) = \Theta(n \log n)$.

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$

Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.

This is tight because $\Omega(n \log n)$ is also a lower bound since: $$ T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n). $$

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$

Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.

This is tight because $\Omega(n \log n)$ is also a lower bound since: $$ T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n). $$

To summarize, you have $T(n) = \Theta(n \log n)$.

Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then $$ T(n) \le 99T( \frac{n}{100} ) + n \log n $$

Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed: $n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.

This is tight because $\Omega(n \log n)$ is also a lower bound since: $$ T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n). $$