Talk:Linearithmic function

This is the talk page of a redirect that targets the page:
• Time complexity
Because this page is not frequently watched, present and future discussions, edit requests and requested moves should take place at:
• Talk:Time complexity

Naming

In keeping with current naming conventions, I propose this article be moved to Linearithmic function (noun, instead of adjective). Any objections? - dcljr (talk) 03:26, 7 August 2006 (UTC)[reply]

I've made the move. - dcljr (talk) 20:11, 10 November 2006 (UTC)[reply]

Sources

This is supposed to have come from Robert Sedgewick's "Algorithms In C" as is widely quoted on the Net... can anyone verify this?

CRGreathouse (t | c) 20:18, 7 June 2007 (UTC)[reply]

This is pretty much to be found in any book on algorithms and data structures... I just call it N log N, never heard the linearithmic name, but it sounds nice and makes sense. --WiseWoman (talk) 20:55, 28 January 2008 (UTC)[reply]

I was just looking for a source on the name, which I had never heard either. CRGreathouse (t | c) 22:39, 28 January 2008 (UTC)[reply]

Also, a source for the name would clarify whether the term can refer only to n log n or also $n\log ^{k}n$ . CRGreathouse (t | c) 18:38, 13 May 2008 (UTC)[reply]

I just found my copy of Robert Sedgewick's "Algorithms In C", 1992. On page 70 in a list of running times it says:

N log N

This running time arises for algorithms that solve a problem by breaking it up into smaller subproblems, solving them independently, and then combining the solutions. For lack of a better adjective (linearithmic?), we'll say that the running time of such an algorithm is "N log N." When N is a million, N log N is perhaps 20 million. When N doubles, the running time more than doubles (but not much more).

Jdougan (talk) 04:44, 11 September 2009 (UTC)[reply]