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 -0000 1.18 +++ ./lib/libc/stdlib/qsort.3 3 Mar 2015 15:56:42 -0000 @@ -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
