Score:1

# 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?](https://crypto.stackexchange.com/q/5832/18298) 2) [How small is negligible?](https://crypto.stackexchange.com/q/61739/18298) 3) [What are not non-negligible functions?](https://crypto.stackexchange.com/q/100177/18298) 4) [Identifying negligible functions](https://crypto.stackexchange.com/q/63284/18298)
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$"
@Mikero you are right about it. Instead of $\lambda_d$ another symbol much easier to grasp.
I sit in a Tesla and translated this thread with Ai: