# What Mathematica features and idioms have n^2 complexity or worse

Here are a few: AppendTo[data, elem], Sort[data, test], in some cases use of ___ (as mentioned in David Wagner's book).

Edit:

A Wolfram Research developer explains here why Union[data,test] has quadratic complexity, and I am pretty sure the same applies to Sort[data,test]. The same Worfram developer explains here that AppendTo[data,elem] has quadratic complexity. There are many math problems such as Inverse[natrix], FactorInteger[n] that are inherently expensive on large problems.

The most important answers to this question will be features in the core language that can kill the performance of a program. Sometimes you can greatly improve the performance of your program if you avoid such features.

-
Ted -- The question might inform a wider audience if you provide some background/explanation of n^2 complexity and it hazards, especially as related to a language like Mathematica, which does so much symbolically. I can imagine that Mathematica's paradigm might have significant vulnerabilities to cascading into complexity. –  Jagra Jul 19 '13 at 18:53
Well, this is going to be a long list. Also: are you sure about Sort[data,test]? Generally, sorting is O(n log n). Check out Trace[Sort[{4, 3, 2, 1}, OrderedQ[{#1, #2}] &]] // Column. My guess is that Mathematica assumes that the function supplied as the second argument is one that yields an ordering on the supplied list, even though the user is free to supply a function that does not satisfy this. For example: Sort[{4, 3, 2, 1}, RandomChoice[{True, False}] &]. Mathematica therefore does not have to compare every two elements. For some fixed tests like 2*Prime[#] < Prime[#2]& ... –  Jacob Akkerboom Jul 19 '13 at 19:50
Anyway I think you are technically right but the statement is a bit vague otherwise, as the test itself can be arbitrarily hard. Also I think the statement about AppendTo is not really well defined. The encoding size of a pointer/reference to a list is very small. But I'd say discussing AppendTo is confusing at least. If we look at Append instead, I guess Append[{a1, a2, ... an}, b] is just O(n). It is "at most" (i.e. it is also) O(n log(n)) as sorting is O(n log(n)) and this also requires you to make a copy of the list ;). –  Jacob Akkerboom Jul 19 '13 at 20:26
@m_goldberg Could you provide a link? –  belisarius Jul 20 '13 at 13:19
@m_goldberg I would prefer it if there is a separate Q&A for this matter (as is currently the case). Especially because this complexity stuff tends to confuse people, myself included :). For example, this answer most likely confuses the concepts of big O notation and Theta notation and still got 2800 upvotes. –  Jacob Akkerboom Aug 8 '13 at 10:34