views:

314

answers:

6

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
Also, why is "double-you double-you double-you" (9 syllables) shorthand for "world wide web" (3 syllables) ???
Joe Koberg
This is true, but linear is longer than `n` and people say that.
Matthew Flaschen
@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
@Joe - at work, I heard a lot of people say "dub-dub-dub"
DVK
@tvanfosson - nice timing :)
DVK
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
@Joe what about just "web"?
isme
www? That is *so* not Web 2.0!
anon
"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
@DVK -- great minds?
tvanfosson
+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
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
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
A: 

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
+14  A: 

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
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
I suspect "original material" on that entry. ..."Results 1 - 10 of about 1,080 for linearithmic." google.com/search?q=linearithmic
Joe Koberg
I get 9600 hits for that search.
Nitrodist
"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
Never heard that (-0.5), never read that (-0.5).Total (-1)
Pavel Shved
"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
You keep saying "linearithmic" and I keep hearing "Eurythmics" -- guess I'll stick with `n log n` or loglinear.
tvanfosson
@Pavel: -1 because you've never heard of or read the book he's citing as a reference? *Seriously?*
Roger Pate
@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
@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
+11  A: 

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

isme
Of those three, only loglinear is somewhat clear in what it means. Though the other two certainly sound kinda cool.
Daniel DiPaolo
"Results 1 - 10 of about 1,080 for linearithmic." http://www.google.com/search?q=linearithmic
Joe Koberg
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
wikipedia has spoken. I'm going to start using linearithmic.
rmeador
+3  A: 

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

JensenDied
Or perhaps "O shit"? :)
jemfinch