What is a constant when talking about asymptotic bounds

31 Views Asked by At

For example I have the function in Johnsonbaugh's book: $$n\log_{2}(n/4)$$ and it concludes that $$\log_{2}n!=\Omega(n\log_{2}n)$$ My question is what exactly is a constant in this case? Are constants positive integers? Real numbers? And in this case what is the constant in $$n\log_{2}(n/4)$$

1

There are 1 best solutions below

3
On

By Stirling's approximation

$$\log_{2}n! \sim \log_{2}\left(\sqrt{2 \pi n}\left(\frac{n}{e}\right)^n\right)\sim n\log_2 (n/e)=n(\log_2 n-\log_2 e)$$

and

$$n\log_{2}(n/4)=n(\log_2 n-\log_2 4)$$