Talk:Linearithmic function

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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]