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}} &\text{if}\, n =2k+1\\ n^{1+\frac{1}{n}}&\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 & \text{if }n=1\\2^{2^{\left\lfloor \log_2\log_2 n \right\rfloor+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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.