By definition $\frac {1} {n}$, $\frac{1}{2^n}$ and $\frac{1}{n!}$ are negligible functions.

I have got the function $$f(n) = \frac{1}{(2^n)!}$$ where $n$ is security parameter.

I don't understand, How do I formally proof that $$\frac{1}{(2^n)!}$$ is a negligible function? Can anyone please help me out?


The simplest way to prove a function $f$ is negligible if it is obviously negligible is to show that it is "more negligible" than some other function $g$ which you have already proven negligble, e.g. $g(n)=2^{-n}$.

Because $g$ is negligble, there exists $n_{g_0}$ such that for all $n>n_{g_0}$ it holds that $g(n)<1/{n^c}$ for any fixed choice of $c$.

Now you can capitalize on that by showing that there exists some $n_{f_0}$ such that for all $n>n_{f_0}$ it holds that $f(n)\leq g(n)$. Clearly it then holds that for all $n>\max(n_{f_0},n_{g_0})$ that $f(n)\leq g(n)<1/n^c$ which means $f$ is negligible.

I'll leave the choice of $g$ for your concrete application to you.

| improve this answer | |
  • $\begingroup$ I, usually, find the limit definition much easier to play. $\endgroup$ – kelalaka Aug 24 '19 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.