0
$\begingroup$

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.

  • 1
    Sidenote: Whenever you have $f(O(h(n)))$ on the RHS, it generally means that you can put the LHS inside $f^{-1}(\cdot)$ and it will be $O(h(n))$. For example, here we have $-\frac{\log f(k)}{\log k}=\omega(1).$2011-09-30

1 Answers 1

1

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

  • 0
    @Shahab it could be.2011-09-30