Definition talk:Big-O Notation

From ProofWiki
Jump to navigation Jump to search

The definition of big O is different. It does not use limits, and certainly doesn't suppose that such a limit exists.--barto (talk) 18:28, 3 December 2016 (EST)

If you have a reliable source, you should add a separate definition according to the one in your source. Then, I would recommend adding a page showing that they are equivalent, or showing a counterexample if they're not equivalent. --GFauxPas (talk) 20:42, 3 December 2016 (EST)
Actually, if the definition you're referring to is the one used in the "implied constant", I think it would be a good idea to extract it and put it as a second definition. And then someone should prove their equivalence or non-. --GFauxPas (talk) 21:12, 3 December 2016 (EST)
There's a definition using limits on Wikipedia, but it lacks cohesion.
I remember that Introduction to Algorithms goes into considerable detail on the subject, but it's right at the bottom of a massive pile of all sorts of books and I wasn't planning on getting it out today.
This page was originally written, in substantially the same format, back in 2009 before we started investing effort into providing citations. The writer was a PhD student, I believe, so I was prepared to take his word for it. --prime mover (talk) 02:19, 4 December 2016 (EST)
It is possible that in computer science they use the simplified definition using limits, because they only consider some simple functions there, such as $n^\alpha(\log n)^\beta$. In mathematics, we do not restrain ourselves to such simple cases and Big-O is defined otherwise. This is why I'd rather not base any definitions in asymptotic analysis ($O$, $o$, $\asymp$, $\sim$, $\ll$ are the most common, as well as their non-uniform versions $O_\alpha$, $o_\alpha$, etc) on what can be found in books on computer science or (complexity of) algorithms. To convince you, the most common version of the prime number theorem is stated as $\pi(x)-x/\log x=O(x/\log^2x)$, but this does not imply that their quotient has a nonnegative limit! In asymptotic analysis we really don't care about the limit.
What I propose: Include the proper definition (with "implied constants", as you call it) and mention the computer-science definition in a remark. --barto (talk) 13:36, 24 January 2017 (EST)

Any ideas to make this page less messy are welcome. I've thought of restricting the scope of the onlyinclude tags to what is essential. Maybe some of the subpages deserve a separate page, such as the one about parameter-dependent estimates. --barto (talk) 06:43, 30 July 2017 (EDT)