qsort.3 big O notation
i was looking at the qsort(3) man page, and saw O N lg N, etc. first i thought, maybe there should be some fancy utf8 math parentheses around, but looking at the source, no, it's plain ascii. a quick search in other man pages reveals an arguably more readable style: ./share/man/man3/queue.3:overhead at the expense of O(n) removal for arbitrary elements. ./share/man/man3/tree.3:and n inserts on an initially empty tree as O((m + n)lg n). ./share/man/man3/tree.3:The amortized cost for a sequence of m accesses to a splay tree is O(lg n). ./share/man/man3/tree.3:Every operation on a red-black tree is bounded as O(lg n). ./share/man/man5/pf.conf.5:If there are 50 rules, all of them are evaluated sequentially in O(n). ./share/man/man5/pf.conf.5:searches in O(log2 n). i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... -f -- if it wasn't for time everything would happen at once. Index: ./lib/libc/stdlib/qsort.3 === RCS file: /cvs/src/lib/libc/stdlib/qsort.3,v retrieving revision 1.18 diff -u -p -r1.18 qsort.3 --- ./lib/libc/stdlib/qsort.3 29 Jan 2015 01:46:31 - 1.18 +++ ./lib/libc/stdlib/qsort.3 3 Mar 2015 15:56:42 - @@ -109,9 +109,9 @@ algorithm, a variant of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. .Fn qsort -takes O N lg N average time. +takes O(n log n) average time. This implementation uses median selection to avoid its -O N**2 worst-case behavior. +O(n**2) worst-case behavior. .Pp The .Fn heapsort @@ -120,7 +120,7 @@ function is an implementation of J.W.J. algorithm, a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. .Fn heapsort -takes O N lg N worst-case time. +takes O(n log n) worst-case time. This implementation of .Fn heapsort is implemented without recursive function calls. @@ -133,7 +133,7 @@ requires additional memory of size bytes; it should be used only when space is not at a premium. .Fn mergesort is optimized for data with pre-existing order; its worst case -time is O N lg N; its best case is O N. +time is O(n log n); its best case is O(n). .Pp Normally, .Fn qsort
Re: qsort.3 big O notation
frantisek holop wrote: i was looking at the qsort(3) man page, and saw O N lg N, etc. first i thought, maybe there should be some fancy utf8 math parentheses around, but looking at the source, no, it's plain ascii. a quick search in other man pages reveals an arguably more readable style: ./share/man/man3/queue.3:overhead at the expense of O(n) removal for arbitrary elements. ./share/man/man3/tree.3:and n inserts on an initially empty tree as O((m + n)lg n). ./share/man/man3/tree.3:The amortized cost for a sequence of m accesses to a splay tree is O(lg n). ./share/man/man3/tree.3:Every operation on a red-black tree is bounded as O(lg n). ./share/man/man5/pf.conf.5:If there are 50 rules, all of them are evaluated sequentially in O(n). ./share/man/man5/pf.conf.5:searches in O(log2 n). i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If that's the argument to be made, it should be log2 as in pf.conf.
Re: qsort.3 big O notation
On Tue, Mar 03, 2015 at 05:02:39PM +0100, frantisek holop wrote: i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If anything, it should be log because that is the name of the mathematical function. libm is completely irrelevant in this context. Joerg
Re: qsort.3 big O notation
Ted Unangst, 03 Mar 2015 11:13: frantisek holop wrote: i was looking at the qsort(3) man page, and saw O N lg N, etc. first i thought, maybe there should be some fancy utf8 math parentheses around, but looking at the source, no, it's plain ascii. a quick search in other man pages reveals an arguably more readable style: ./share/man/man3/queue.3:overhead at the expense of O(n) removal for arbitrary elements. ./share/man/man3/tree.3:and n inserts on an initially empty tree as O((m + n)lg n). ./share/man/man3/tree.3:The amortized cost for a sequence of m accesses to a splay tree is O(lg n). ./share/man/man3/tree.3:Every operation on a red-black tree is bounded as O(lg n). ./share/man/man5/pf.conf.5:If there are 50 rules, all of them are evaluated sequentially in O(n). ./share/man/man5/pf.conf.5:searches in O(log2 n). i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If that's the argument to be made, it should be log2 as in pf.conf. oops. (my compsci classes were in another millenium) -f -- if practice makes perfect, and nobody's perfect, why practice?
Re: qsort.3 big O notation
Joerg Sonnenberger, 03 Mar 2015 17:28: On Tue, Mar 03, 2015 at 05:02:39PM +0100, frantisek holop wrote: i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If anything, it should be log because that is the name of the mathematical function. libm is completely irrelevant in this context. 'lg' is also a valid name (altough i admit i didn't know, i was used to log2) https://en.wikipedia.org/wiki/Logarithm#Particular_bases as Tedu pointed out lg = log2 and lg != log but i think my point is still kind of valid, as there is log2(3) and no lg(3). i find it relevant that libm should also use the most common, easiest names where possible... it is kind of nice to be able to do 'man log2' after reading 'man qsort', a kind of indirect cross reference. -f -- illiterate? write for a free brochure!
Re: qsort.3 big O notation
On March 3, 2015 at 5:48 PM frantisek holop min...@obiit.org wrote: If anything, it should be log because that is the name of the mathematical function. libm is completely irrelevant in this context. 'lg' is also a valid name When talking about big O notation, you want to trim as many constants as possible. I would go for log, too: log2(x) can be written as log(x)/log(2), which means that 1/log(2) is the constant that you can remove: log(x) is left.
Re: qsort.3 big O notation
On 3 March 2015, frantisek holop min...@obiit.org wrote: Joerg Sonnenberger, 03 Mar 2015 17:28: On Tue, Mar 03, 2015 at 05:02:39PM +0100, frantisek holop wrote: i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If anything, it should be log because that is the name of the mathematical function. libm is completely irrelevant in this context. 'lg' is also a valid name (altough i admit i didn't know, i was used to log2) https://en.wikipedia.org/wiki/Logarithm#Particular_bases as Tedu pointed out lg = log2 and lg != log Actually, that isn't what Tedu said, and it isn't the generally accepted convention. The usual convention is: * log = ln = log_e * lg = log_10 As somebody else points out, they differ from each other by multiplicative constants, so either are correct for O-notation. (Full disclosure: I'm a mathematician. :)) but i think my point is still kind of valid, as there is log2(3) and no lg(3). i find it relevant that libm should also use the most common, easiest names where possible... it is kind of nice to be able to do 'man log2' after reading 'man qsort', a kind of indirect cross reference. Regards, Liviu Daia
Re: qsort.3 big O notation
In the most recent algorithms lecture I heard we used log for base 2, ln for base e, and lg for base 10. But asymptotically the base doesn't matter and the notation coventions differ. So I'd also go for consistency with other documentation. On March 3, 2015 5:48:20 PM CET, frantisek holop min...@obiit.org wrote: Joerg Sonnenberger, 03 Mar 2015 17:28: On Tue, Mar 03, 2015 at 05:02:39PM +0100, frantisek holop wrote: i leave the battle about lg vs log to others, but i prefer 'log' as there is a man page for that and there is none for 'lg'... If anything, it should be log because that is the name of the mathematical function. libm is completely irrelevant in this context. 'lg' is also a valid name (altough i admit i didn't know, i was used to log2) https://en.wikipedia.org/wiki/Logarithm#Particular_bases as Tedu pointed out lg = log2 and lg != log but i think my point is still kind of valid, as there is log2(3) and no lg(3). i find it relevant that libm should also use the most common, easiest names where possible... it is kind of nice to be able to do 'man log2' after reading 'man qsort', a kind of indirect cross reference. -f -- illiterate? write for a free brochure! -- Sent from my Android device with K-9 Mail. Please excuse my brevity.
Re: qsort.3 big O notation
Liviu Daia, 03 Mar 2015 19:26: 'lg' is also a valid name (altough i admit i didn't know, i was used to log2) https://en.wikipedia.org/wiki/Logarithm#Particular_bases as Tedu pointed out lg = log2 and lg != log Actually, that isn't what Tedu said, and it isn't the generally accepted convention. The usual convention is: my mistake. * log = ln = log_e * lg = log_10 As somebody else points out, they differ from each other by multiplicative constants, so either are correct for O-notation. (Full disclosure: I'm a mathematician. :)) yes, these are the ISO notations from that wikipedia page. that Other notations for binary are quite liberal (ld, log, log2, lg) if all is the same, then i find 'log' the most readable in a man page. -f -- all computers wait at the same speed.
