# What Mathematica features and idioms have $n^2$ complexity or worse [closed]

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 Wolfram developer explains here that AppendTo[data,elem] has quadratic complexity. There are many math problems such as Inverse[matrix], 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. 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]& ... Jul 19 '13 at 19:50
• We already have a "pitfalls" community wiki. I think this fits under that umbrella and would the answer should be made there. Jul 20 '13 at 1:43
• @m_goldberg Could you provide a link? 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. Aug 8 '13 at 10:34