what is the relation between two functions ?

Question

A) nlg c  , clg n ,  

B) lg(n!) , lg(nn)

I guess both are equivalent so then how to represent them using asymptotic notation ?

Answer 1

A.

$n^{\lg c} = n^k $ has polynomial growth since $ k = \lg c $ is a constant.

$c^{\lg n}$ is exponential in $\lg n$ and hence $O(n).$

So, $$n^{\lg c} = \Theta\left(c^{\lg n}\right).$$

B.

$\lg (n^n) = n \lg n$

$\lg (n!) = \Theta ( n \lg n)$ (Stirling's approximation)

So, $$\lg (n!) = \Theta(\lg n^n).$$

Comments

http://math.stackexchange.com/questions/664831/is-n-log-c-c-log-n-true

---

Sorry. Exponential in log n is linear in n. I have corrected..

---

Sir according to symmetric property we can write then c^log n =theta(n^log c) right so then there is nothing like exponential growth and polynomial growth then I guess .