Are Big-Theta functions asymptotic monotonically non decreasing?
No, it may not be true. 

Consider the following function on $\Bbb N$.

$$f(n)=\begin{cases}
(n+2)^2\quad &amp;\text{when } n \text { is odd,}\\
n^2\quad &amp;\text{when } n \text { is even.}\\
\end{cases}$$

Then $f(n)=\Theta(n^2)$. However, for all odd $n$, $f(n)&gt;f(n+1)$. In fact, $f(n)-f(n+1)\to\infty$ when $n$ goes to $\infty$ along the odd numbers.



Here are two related exercises.

Exercise 1. Give an example of $f(n)=\Theta(n)$ such that $f(n)&gt;f(n+1)$ for infinitely many $n$.

Exercise 2. Let $g(n)\ge0$ be an unbounded function on $\Bbb N$.


Let $h(n)=\Theta(g(n))$. Prove that $h(n)&lt;h(n+1)$ for infinitely many $n$.
Construct $f(n)=\Theta(g(n))$ such that for any number $c$, $f(n)-f(n+1)&gt;c$ for infinitely many $n$.