When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and asymptotically monotonically increasing. I mean that for all $n$ greater than or equal to some $n_0$ both those properties hold?


2 Answers 2


It is safe to assume that $f$ is everywhere positive, hence, asymptotically positive. You can't use negative time or space.

It is not safe to assume that $f$ is asymptotically monotonically increasing, since this excludes constant functions, i.e., those which are $\Theta(1)$.

It isn't even safe to assume that $f$ is asymptotically monotonically non-decreasing; this precludes functions that oscillate. A good question might be "do any useful algorithms have asymptotically oscillating time or space complexities," but certainly you could create an algorithm that did.

I suppose a more rigorous answer would ask what your definition of "asymptotically monotonically increasing" means. If it means that it's $\Theta(g(n))$ where $g(n)$ is monotonically increasing for positive $n$, then the answer would be yes, by definition.

  • $\begingroup$ In Cormen it says: "A function f(n) is monotonically increasing if $m \leq n$ implies $f(m)\leq f(n)$". Wouldn't this allow constant functions? What you're describing sounds like what Cormen calls "strictly increasing". $\endgroup$ Commented Mar 21, 2013 at 11:27
  • $\begingroup$ Are there real algorithms whose worst case run time behave like $\sin^2 n + 1$? I.e. are asymptotically positive, oscillate and have tight upper and lower bounds? $\endgroup$ Commented Mar 21, 2013 at 11:51
  • 1
    $\begingroup$ @RobertS.Barnes Two things: (1) If that's how Cormen defines "monotonically increasing", then Cormen is using a non-standard definition. What Cormen calls "monotonically increasing" most mathematicians (as far as I'm aware) would refer to as "monotonically non-decreasing". Monotonically increasing would be: $m < n$ implies $f(m) < f(n)$. (2) There aren't any algorithms with that runtime, but that's just because that function only assumes an integer value for $n = 0$; this can be easily resolved, however. Such a function would be $\Theta(1)$, since it's bounded below by $1$ and above by $2$. $\endgroup$
    – Patrick87
    Commented Mar 21, 2013 at 15:23

No. There are complexity functions that oscillate, for example runtime of Mergesort.

It is not even true that every meaningful complexity function is in $\Theta$ of a monotonically increasing function; see this answer to your older question.

  • $\begingroup$ So the worst case run time of Mergesort oscillates within $n \lg n$ upper and lower bounds? $\endgroup$ Commented Mar 21, 2013 at 11:24
  • $\begingroup$ @RobertS.Barnes Yes. (To be precise, $\Theta(n \log n)$ bounds.) Obviously, since its $\Theta$-runtime is $\Theta(n \log n)$. $\endgroup$
    – Raphael
    Commented Mar 21, 2013 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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