Why drop the parentheses? Mathematical function application notation usually uses parentheses; I would find this change both unconventional and unsightly. Note also that we sometimes say things like "log(a - b)" where we need the parentheses anyway.

We say $N \log N$ fairly often (in the containers section); the algorithms section uses $N \log(N)$ more often. This is an attempt to harmonize towards $N \log N$.
My impression is that for single-token arguments in complexity expressions, it is sort-of common to omit the parenthesis, but maybe I'm mistaken.

If you end up using nested parentheses (e.g., \bigoh{log(a - b)}$), then you should consider using larger parentheses on the outside (e.g., \mathscr{O}\big(log(a - b)\big)$).

@godbyk: Yes, except I thought math mode would auto-scale such things? Anyway, the uses I've come across in our standard use just "N" or "N log N" and then define what N means in an extra phrase. I haven't come across nested parens, yet, except possibly for \bigoh{\log(N)}, which the proposed patch will fix (by removing the inner set of parens).

@jensmaurer I'm afraid there's no such autoscaling. The closest autoscaling would be using \left( and \right), but those won't scale up unless the material inside them exceeds the vertical height of the normal parentheses—and $log(a - b)$ wouldn't. If you wrote $\left( log ( a - \frac{(n-1)n}{2} ) \right)$ then the outer parentheses would autoscale.

You can use \bigl(, \Bigl(, etc. (but only the first one fits on a normal line). But... that should be considered with utmost care and restraint.

Rebased.

I prefer log(N) to log N so as not to run into ambiguity issues with what log a + b means

@burblebee: See #1088 for the editorial direction.

@zygoloid: This seems ready to merge.