Timeline for Asymptotic Properties of Functions in Complexity Analysis
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 29, 2013 at 7:18 | vote | accept | Robert S. Barnes | ||
| Mar 21, 2013 at 15:23 | comment | added | Patrick87 | @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$. | |
| Mar 21, 2013 at 11:51 | comment | added | Robert S. Barnes | 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? | |
| Mar 21, 2013 at 11:27 | comment | added | Robert S. Barnes | 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". | |
| Mar 20, 2013 at 20:45 | history | answered | Patrick87 | CC BY-SA 3.0 |