I am struggling with logarithms and their computation when it comes to computing time complexity.
I have a simple complexity: $\frac{1}{n^{\lg (n)}}$, where the logarithm base is 2. How can I reduce this to some simplier form? I know that the answer is 2 but I was unable to see why?
I know I can begin the reduction like this (please, correct me, if I am wrong):
$\frac{1}{n^{\lg (n)}} = 2^{\lg\frac{1}{n^{\lg (n)}}} = 2^{\lg (1) - \lg(\lg(n^{\lg (n)}))}$ ... but I do not know how to do the next step.. Thanks for any help!
$n^{\log_2 n} = 2^{\log_2 n\cdot \log_2 n} = 2^{\log_2^2 n}$, using $b^a = 2^{a\log_2 b}$. This is not equal to $1/2$, far from it (so equivalently, $\frac{1}{n^{\log_2 n}} \neq 2$).
$2^{\log_2^2 n}\xrightarrow[n\to\infty]{}\infty$, and "very fast": it is non-polynomial (every polynomial $p$ has $p(n)=o(2^{\log_2^2 n})$); it is commonly referred to as quasipolynomial, being "between" polynomial ($2^{c\log_2 n}$ for a constant $c> 0$) and exponential ($2^{cn}$ for some constant $c>0$) in terms of growth.