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