# asymptotics – A monotonically nondecreasing function \$ f(n) \$ s.t \$ f in O(n^2) \$ and \$ f notin o(n^2) \$ but also \$ f in Omega(n) \$ and \$ f notin omega(n) \$

I may be wrong, but it seems to me that the function defined by:

$$f(n) = left{begin{array}{rl}1 & text{if }n=1\2^{2^{leftlfloor log_2log_2 n rightrfloor+1}}&text{otherwise}end{array}right.$$

satisfy the conditions.

To explain why, the values taken by $$f(n)$$ will be $$1, 4, 4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 256, 256, …$$

The idea is that when $$n=2^{2^k}$$, then $$f(n) = 2^{2^{k+1}} = n^2$$, and when $$n=2^{2^k}-1$$, then $$f(n) = 2^{2^{k}} = n +1$$. That way, you will guarantee the 5 conditions: $$(O(n^2) setminus o(n^2)) cap (Omega(n) setminus omega(n))$$ and increasing.