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?
$\begingroup$
$\endgroup$
asked Mar 20, 2013 at 20:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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$ Commented Mar 21, 2013 at 15:23
$\begingroup$
$\endgroup$
2
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$– RaphaelCommented Mar 21, 2013 at 12:03