Identifying negligible functions I am having a hard time understanding and applying the formulas that are used to identify a function is negligible or not?


One text defines it as; a function $f$ from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial $p$ there is an $N$ such that for all integers $n &gt; N$ it holds that $f(n) &lt; 1/p(n)$.
Another textbook defines it as; a function $f$ is negligible if, for every polynomial $p$, we have $\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda)=0$


Example: $1/2^{\lambda/2}$ would this be considered as negligible function?
From the first definition;


To see that a function is negligible, you have to find an $n &gt;N$ for every positive polynomial $p(n)$ such that after $f(n) &lt; 1/p(n)$ is holds. Here two examples;


consider $p(n)= 10^6$ then $n \geq 800$ then $1/2^{800/2} = 1/1048576 &lt; 1/10^{-6}$
consider $p(n)= 10^{3}$ then $n \geq 200$ then $1/2^{200/2} = 1/1024 &lt; 1/10^{-3}$



  From the second definition;
  $\lim_{\lambda \rightarrow \infty} p(\lambda) f(\lambda) =0?$


For your $f(\lambda) = 1/2^{\lambda/2}$ we have to see that the limit is 0 whatever the polynomial $p(\lambda) = a_n \lambda^n +\ldots + a_0$ 

$$\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda) = \frac{p(\lambda)}{2^{\lambda /2 }} = \lim_{\lambda \rightarrow \infty} \frac{a_n \lambda^n +\ldots + a_0}{2^{\lambda /2 }} = 0,$$

since if you take the L'Hôpital's rule the $n$-times the numerator will be 1 and eventually zero. The denumerator, however, goes to infinity.