# Physical meaning of Negligible and Non-Negligible Functions

I've been itching my head over this for a while despite going through the queries related to the topic. Can someone explain me negligible and non-negligible function in a concise way?

As of my naive understanding (correct me if I've the wrong take);

A non-negligible function is one which approaches zero relatively slow (eg: reciprocal of polynomial function as compared to exponential function) and given enough computationally possible time and space, such function is breakable after, poly(n) time.

A negligible function is one which approaches zero quickly and is computationally infeasible to break as the function grows faster with time. e.g. $$\frac{1}{k^n}$$

I don't understand how $$\epsilon(\lambda) \geq \frac{1}{\lambda^n}$$ is non-negligible and $$\lambda \geq \lambda_d: \epsilon(\lambda) \leq \frac{1}{\lambda^n}$$ is negligible. Also, what's $$\lambda_d$$ suppose to mean?

• Do you want something like these? 1) What exactly is a negligible (and non-negligible) function? 2) How small is negligible? 3) What are not non-negligible functions? 4) Identifying negligible functions Commented Oct 15, 2022 at 17:28
• I don't think $\lambda_d$ is a typo. It is saying, for all $d$, there exists a number $\lambda_d$, such that for all $\lambda \ge \lambda_d$, the function is smaller than $1/\lambda^d$. In other words, for all $d$, the function is eventually smaller than $1/\lambda^d$, and "eventually" means "for all but finitely many $\lambda$", i.e., "for all $\lambda$ larger than some finite limit $\lambda_d$" Commented Oct 15, 2022 at 19:10
• @Mikero you are right about it. Instead of $\lambda_d$ another symbol much easier to grasp. Commented Oct 15, 2022 at 19:26