Timeline for Big O notation and the maximal set of comparable functions
Current License: CC BY-SA 2.5
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2010 at 15:49 | comment | added | Piotr Migdal | @JDH: Thanks. The $lim$ was used in informal context (see: edit note). No, I do not insist on the existence of $\lim f(x)$. | |
| Nov 10, 2010 at 15:44 | history | edited | Piotr Migdal | CC BY-SA 2.5 |
definition changed; deleted 1 characters in body
|
| Nov 10, 2010 at 14:51 | comment | added | Joel David Hamkins | The definition of your relation $\leq$ still doesn't make sense to me. Do you really want to apply the limit only to f on the left? Then to what does x in g(x) on the right refer? And you really want to insist that lim f(x) exists? In this case, an f without a limit is not even related to itself, which is presumably undesired. Probably you want to use the relation I suggested. | |
| Nov 10, 2010 at 14:47 | comment | added | Joel David Hamkins | Piotr, to the contrary, I believe that there is a lot of sophisticated set theory arising in connection with your question. | |
| Nov 10, 2010 at 12:21 | answer | added | Joel David Hamkins | timeline score: 8 | |
| Nov 10, 2010 at 9:55 | comment | added | Piotr Migdal | @JDH: Actually, the use of set theory here is trivial. | |
| Nov 10, 2010 at 9:52 | comment | added | Piotr Migdal | @JDH & TZ & TI: I mistaken the order, but obviously it do not change anything. Thanks. @AKG: "Canonical" - "standard" - "natural" (no, it do not have a precise definition). @TI: Since its about big O notation (the problem itself isn't in ct, but asks about its common tool). @GE: Thanks! | |
| Nov 10, 2010 at 9:47 | history | edited | Piotr Migdal | CC BY-SA 2.5 |
f/g reversed, added 'continuous;
|
| Nov 10, 2010 at 4:47 | answer | added | Yuval Filmus | timeline score: 6 | |
| Nov 10, 2010 at 4:34 | comment | added | Gerald Edgar | Perhaps related to Hamkins answer here: mathoverflow.net/questions/3057/… | |
| Nov 10, 2010 at 3:50 | comment | added | Tsuyoshi Ito | How is this question related to complexity theory? | |
| Nov 10, 2010 at 3:49 | comment | added | Tsuyoshi Ito | @Thierry Zell: I did not realize that until I read your comment (thanks), but I do not know if that is all he meant. The right-hand side of the inequality contains x as a free variable and I do not know what this definition (as is written) means even if we swap f and g. | |
| Nov 10, 2010 at 3:44 | answer | added | Ross Millikan | timeline score: 0 | |
| Nov 10, 2010 at 3:03 | comment | added | Thierry Zell | I think what Joel means in his first comment is that you have switched the order of $f$ and $g$ between the two clauses of your definition. | |
| Nov 10, 2010 at 3:01 | comment | added | Amit Kumar Gupta | What do you mean by "canonical"? | |
| Nov 10, 2010 at 2:53 | comment | added | Joel David Hamkins | Perhaps you want $f\leq g$ iff $\exists C\, f\leq^\ast Cg$, or in other words, $\exists z\forall x\geq z\, f(x)\leq Cg(x)$. | |
| Nov 10, 2010 at 2:28 | comment | added | Joel David Hamkins | I don't think you've defined the order relation how you intended. And I sugges the set-theory tag in place of complexity-theory. | |
| Nov 10, 2010 at 2:13 | history | asked | Piotr Migdal | CC BY-SA 2.5 |