Tuesday, October 11, 2016

Negligible and non-negligible - A better explanation

The page, Negligible and non-negligible, explains what means

lambda >= lambda d 

in the definition of negligible and non-negligible,



by using the below formula,

g(x) = 2^x - x^d >= 0

to draw the below picture,



Actually, we can using another formula to draw a more beautiful picture. We derive the formula as below:

We except that:

f(x) = 1/(2^x) <= 1/(x^d)

We define that:

g(x) = (x^d) / (2^x) <= 1

And draw the below picture for d = 2, 3, 4.




Please look at the red lines:

For d = 2, g(x) <= 1, if x >= 4
For d = 3, g(x) <= 1, if x >= 9.94...
For d = 4, g(x) <= 1, if x >= 16

The values, 4, 9.94..., and 16 are of "lambda d".

-Count

No comments:

Post a Comment