4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\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$ – Robert S. Barnes Mar 21 '13 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$ – Robert S. Barnes Mar 21 '13 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 Mar 21 '13 at 15:23
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So the worst case run time of Mergesort oscillates within $n \lg n$ upper and lower bounds? $\endgroup$ – Robert S. Barnes Mar 21 '13 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 Mar 21 '13 at 12:03

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.