0

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!

Vibhav
  • 627
Smajl
  • 686

1 Answers1

1

$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.

Clement C.
  • 67,323
  • 1
    @Smajl: regarding your original belief that the expression should be equal to $2$, are you certain you didn't make a mistake when writing down the actual expression (I'm assuming from a blackboard)? For $n^{\frac{1}{\log_2 n}}$ does simplify to $2^{\frac{1}{\log_2 n}\cdot\log_2 n}=2^1=2$. – Clement C. Sep 07 '14 at 13:07
  • Interesting... if this is so then another way of looking at it would be $n^{\frac 1{\log_2 {n}}}=n^{\log_n 2}=2$ – Hypergeometricx Sep 07 '14 at 18:48