PLEASE see attachment for proper display of equations.
Let f be a function from N to R+ . Function f is eventually nondecreasing if
such that . Function f is smooth if it is eventually
nondecreasing and such that .
(a) Is the function + such that a smooth function? Verify!
(b) Is the function + such that = a smooth function? Verify!
f(n) = n*log(n), n belong to N.
for m,n belong to N and m <= n:
f(m) = m*lg(m)
f(n) = n*lg(n)
because, lg(n) is slow increasing function, therefore,
f(n) >= f(m)
=> f(n) is non-decreasing function Ok.
for k,n belong to N and ...
Smooth functions are analyzed. Increasing and nondecreasing functions are provided.