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 am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:
$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \omega(n) $. The domain could also be all real numbers.
I considered different variations of piecewise functions, for example I considered the function $$ f(n)=
\begin{cases}
 n^{2-\frac{1}{n}} &amp;\text{if}\, n =2k+1\\
 n^{1+\frac{1}{n}}&amp;\text{if}\, n=2k\\
\end{cases} $$
which satisfies the growth rate conditions, but is clearly not monotonically non-decreasing.
I would be happy to hear your ideas, thank you.
I may be wrong, but it seems to me that the function defined by:
$f(n) = \left\{\begin{array}{rl}1 &amp; \text{if }n=1\\2^{2^{\left\lfloor \log_2\log_2 n \right\rfloor+1}}&amp;\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.