I am reading from some notes on cryptography and came across this sentence: "We call a function f negligible in k if it asymptotically approaches zero faster than any inverse polynomial in k i.e., $f(k) = k^{-\omega (1)}$." Can someone explain to be in simple terms what this means? With an example perhaps.
Thank you.
It means that $\lim_{k\to\infty} f(k)|k|^n=0\;$ for any $n\in \mathbb N$. Or, equivalently, the estimate $|f(k)|\le C |k|^{-n}\ $ holds for large enough values of $k$ and some $C>0$.