Is there a shorthand term for O(n log n)?

views:

314

answers:

+15 Q:

Is there a shorthand term for O(n log n)?

We usually have a single word for most complexities we encounter in algorithmic analysis:

O(1) == "constant"
O(log n) == "logarithmic"
O(n) == "linear"
O(n^2) == "quadratic"
O(n^3) == "cubic"
O(2^n) == "exponential"

We encounter algorithms with O(n log n) complexity with some regularity (think of all the algorithms dominated by sort complexity) but as far as I know, there's no single word we can use in English to refer to that complexity. Is this a gap in my knowledge, or a real gap in our English discourse on computational complexity?

+13 A:

"en log en" has fewer syllables than "exponential" or "logarithmic". I think most people just say that.

Joe Koberg 2010-04-14 17:07:01

Also, why is "double-you double-you double-you" (9 syllables) shorthand for "world wide web" (3 syllables) ???

Joe Koberg 2010-04-14 17:08:16

This is true, but linear is longer than `n` and people say that.

Matthew Flaschen 2010-04-14 17:08:38

@Joe -- perhaps that's why many people just say "dub-dub-dub." Not me, of course, I think that makes you sound like an blibbering idiot.

tvanfosson 2010-04-14 17:10:39

@Joe - at work, I heard a lot of people say "dub-dub-dub"

DVK 2010-04-14 17:11:08

@tvanfosson - nice timing :)

DVK 2010-04-14 17:11:32

Yeah, I remember the TV tech-talk shows covering "the web" in the late nineties trying to work in "dub-dub-dub".... It was terrible.

Joe Koberg 2010-04-14 17:13:31

@Joe what about just "web"?

isme 2010-04-14 17:13:34

www? That is *so* not Web 2.0!

anon 2010-04-14 17:13:39

"dub dub dub"? Really? ...Rub-a-dub-dub-dub? George DubDubDubya Bush? See what kinds of shenanigans you invite if you do this? For the love of all that is good in the world, please do NOT fall into that trap!

Platinum Azure 2010-04-14 18:04:06

@DVK -- great minds?

tvanfosson 2010-04-14 18:29:26

+1 A:

I don't believe there is such a term.

More relevant, though, is this thought: Why do you refer to exponential (11 characters) as a "shorthand" for O(2^n) (6 characters)?

Personally, I'm quite happy to say "this algorithm runs in en log en time". It's all most people need to hear.

Platinum Azure 2010-04-14 17:08:05

Now, say "this algorithm runs in two to the enth time" versus "this algorithm runs in exponential time". The latter is, in my opinion, more idiomatic and easier to say.

David Thornley 2010-04-14 17:52:40

Yeah, I agree with you there. I never claimed that exponential was not easier to say. But I don't believe there's a simple, idiomatic way to express the product of a linear and logarithmic growth function.

Platinum Azure 2010-04-14 18:01:29

No there's no single word equivalent for O(nlogn). You just have to spend the extra time saying the whole thing (Note: same number of syllables as "exponential")

chetan 2010-04-14 17:08:05

+14 A:

O(n log n) == "linearithmic"

Seems to have been coined by Robert Sedgewick in the book Algorithms In C. Also called quasilinear or loglinear. However, linearithmic has the added bonus of not being an overloaded term (quasilinear is used in economics and differential equations, while loglinear is used in economics and regression analysis).

John Calsbeek 2010-04-14 17:08:47

From the looks of other answers, I don't think this is common parlance (I'd never heard of it), so for clarity's sake I'd stick with "inlogin" or you may get some weird looks. +1 though - perhaps in time this'll become a commonplace term (weird that it isn't already).

Ian Henry 2010-04-14 17:13:25

I suspect "original material" on that entry. ..."Results 1 - 10 of about 1,080 for linearithmic." google.com/search?q=linearithmic

Joe Koberg 2010-04-14 17:14:12

I get 9600 hits for that search.

Nitrodist 2010-04-14 17:19:07

"Linearithmic" was coined as a portmanteau of "linear" and "logarithmic" in *Algorithms In C* by Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

John Calsbeek 2010-04-14 17:20:37

Never heard that (-0.5), never read that (-0.5).Total (-1)

Pavel Shved 2010-04-14 17:33:10

"Linearithmic" appears in 32 books per Google Books search results, and has the added bonus (over quasilinear and loglinear) of not being used for other mathematical purposes. If people had heard of it, this question probably wouldn't exist.

John Calsbeek 2010-04-14 17:38:01

You keep saying "linearithmic" and I keep hearing "Eurythmics" -- guess I'll stick with `n log n` or loglinear.

tvanfosson 2010-04-14 18:27:42

@Pavel: -1 because you've never heard of or read the book he's citing as a reference? *Seriously?*

Roger Pate 2010-04-15 09:37:11

@Roger, no, -1 because of pushing a *very* narrowly used term as a correct answer. That wasn't a reply to Calsbeek's comment.

Pavel Shved 2010-04-15 10:26:29

@Pavel: You said -0.5 because you'd not known the answer previously (and what is that about? if *you* haven't heard of it, then it must be wrong?). What was it you'd not read that made up the other -0.5? But even with the new explanation, you're reading your own FUD into this answer; he's merely answering the question with a reference to a well-known book (even if *you* didn't know about it before). Where is he pushing any agenda?

Roger Pate 2010-04-19 01:21:27

+11 A:

According to Wikipedia you can call it linearithmic, loglinear, or quasilinear.

isme 2010-04-14 17:09:03

Of those three, only loglinear is somewhat clear in what it means. Though the other two certainly sound kinda cool.

Daniel DiPaolo 2010-04-14 17:11:32

"Results 1 - 10 of about 1,080 for linearithmic." http://www.google.com/search?q=linearithmic

Joe Koberg 2010-04-14 17:11:33

I prefer 'loglinear' myself. There is also the variant [logilinear](http://www.google.com/search?q=logilinear) in the wild, but this is not officially acknowledged by any dictionary, and seems only to be used in the context of loglinear modelling.

isme 2010-04-14 17:36:54

wikipedia has spoken. I'm going to start using linearithmic.

rmeador 2010-04-14 17:49:18

+3 A:

O(2^n) == "O Scary"

JensenDied 2010-04-14 17:09:49

Or perhaps "O shit"? :)

jemfinch 2010-04-14 17:17:11

ansaurus

tags:

views:

answers:

Is there a shorthand term for O(n log n)?

related questions