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