From the premise for c = 2
, there is an N0 > 0
such that f(n) >= 2 log(n)
for all n > N0
. By monotonicity of y = 2^x
this is equivalent to 2^f(n) >= n^2
for all n > N0
.
For any d > 0
there is an N1 > 0
such that n^2 >= n/d
for all n > N1
since the quadratic n^2
grows faster than any linear n/d
.
Combining the two inequalities, n/d <= n^2 <= 2^f(n)
for all n > max(N0, N1)
.
CLICK HERE to find out more related problems solutions.