I am aware that negligible functions that have a negative fixed power are not negligible. However, I am slightly confused and unsure as to why the following two examples are NOT negligible functions:
$1)~~~~ f(n) = n^{-\log n} ~$
$2)~~~~ f(n) = n^{-512} $
Similarly, I also do not understand why a negligible function $~f~$, is still negligible when it is $~f(n)^{-1}~$ but then a polynomial function $~t~$ that is $~t(n)^{-1}~$ is not negligible.
Been trying to understand this elementary math but I been breaking my head for too long. Would be amazing if someone could give me an explanation for each one as to why it is NOT negligible, as my understanding of negligible functions were that negative powers are always negligible.
.....
From Wikipedia:
In mathematics, a negligible function is a function $\mu : \mathbb N \to \mathbb R$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$, $$|\mu (x)|<{\frac {1}{x^{c}}}.$$
For $f(n) = n^{-512}$ note that for $c = 513$ you never get $$ |f(n)| < \frac{1}{n^c} \quad\text{that is} \quad\frac{1}{n^{512}} < \frac{1}{n^{513}} . $$ Thus the clause "for every positive integer $c$" fails, since there is at least one (namely $c=513$) where it is false.
Next consider $f(n) = n^{-\log n}$. Note $$ n^{-\log n} < \frac{1}{n^c} \tag1$$ if and only if $$ -\log n < -c \tag2$$ if and only if $$ \log n > c \tag3$$ We know $\log n \to \infty$ as $n \to \infty$, which means: for every $c$, there is $N_c$ so that $(3)$ holds for all $n > N_c$. We conclude $n^{-\log n}$ is negligible.