Timeline for Sorting functions by asymptotic growth
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 19, 2018 at 8:50 | comment | added | Raphael | @Apass.Jack Now that would probably make for a useful answer for non-students (= favor result over gaining method skills). I hope we can agree that dumping a (wrong) table here isn't it. | |
| Oct 19, 2018 at 8:40 | comment | added | John L. | @Raphael, I agree with many of your points, although for each of them, there is also another side of the story. The practical way to move forward here is, could someone add some simple explanation of the table. Summarize some of the patterns. Use a few examples to show how to take the most advantage of this table, for example, how to guess the right asymptotic behavior of functions not in the table such as a change of variable. | |
| Oct 19, 2018 at 8:18 | comment | added | Raphael | @kelalaka "Yes, Landau is more about a specific type of algorithm in Cryptography." -- that doesn't even make sense. Landau notation is a shorthand to describe properties of mathematical functions. It has nothing to do with algorithms let alone cryptography, per se. | |
| Oct 19, 2018 at 8:17 | comment | added | Raphael | @Apass.Jack In my teaching experience, when given a table many students will learn it by heart and fail to order wrt any function not in the table. Note how that effect seems to account for many of questions regarding asymptotic growth that land on this site. That said, of course we'll use lemmata implied by the table if it makes proofs easier, but that comes after learning how to proof the table. (To emphasize that point, people who come here don't need help reading stuff off a table. They need help proving relations.) | |
| Oct 19, 2018 at 8:13 | comment | added | Raphael | The issue remains that the question is about Landau classes, not complexity classes. And also, again, "Factorial time" is not larger than "Exponential time"; it is, in fact, strongly included. | |
| Oct 19, 2018 at 6:40 | comment | added | John L. | I object to some of @Raphael's views. I have been a mathematician and an instructor for many years. I believe, apart from proving those things, a big table like this increases people's intuition easily and greatly. And the names of the asymptotic classes help people remember and communicate a lot. | |
| Oct 19, 2018 at 6:27 | comment | added | kelalaka | I put this so the name of the complexity classes can be talked directly here. Yes, Landau is more about a specific type of algorithm in Cryptography. | |
| Oct 19, 2018 at 6:19 | history | edited | kelalaka | CC BY-SA 4.0 |
removed double exponential time.
|
| Oct 19, 2018 at 6:13 | comment | added | Raphael | Also, interesting how the table suggests that $2^{n \log n} \in o(n!)$. While the table you link to is somewhat accurate, the one linked there (and which you copied) is about complexity classes, which is not a helpful thing to mix in here. Landau notation is not about "time". | |
| Oct 19, 2018 at 6:11 | comment | added | Raphael | This doesn't add much over Robert S. Barnes', and misses the point of this reference completely. It's about proving those things (and gaining intuition), not consulting tables. And also, there's little point to copy-paste material from Wikipedia. We can assume posters already went there. | |
| Oct 19, 2018 at 5:41 | history | edited | kelalaka | CC BY-SA 4.0 |
added link to Wikipedia.
|
| Oct 6, 2018 at 15:18 | history | answered | kelalaka | CC BY-SA 4.0 |