RBarryYoung (6/13/2009)

---

Jeff Moden (6/12/2009)

---

RBarryYoung (6/10/2009)

---

Jeff Moden (6/10/2009)

---

If you strip away all the small stuff that won't impact the result much when the numbers get really big, you end up with O(N²/2). That's much easier to compare to a cartesian join which is both N² and O(n²) to say that a triangular join is approximately half as bad as the square join.

Actually, you strip away the constant factors (like 1/2) too, so that the complexity order is also O(n²). Thus the complexity of all square and all triangular algorithms have the same order.

Understood and I agree. The point I was really trying to make is that for all values this side of infinity that will still fit inside SQL Server, the /2 is important. 😛

Yes, but the point is that you do not use constant factors like the /2 in big-O notation or the "complexity order" of something. This is because the purpose of complexity order analysis is to separate algorithmic efficiency (the converse of complexity), from implementation efficiency which is dependent on HW performance, SW efficiency, and the developer's code efficiency.

What this means is that an efficiently implemented Square algorithm can beat an inefficient Triangular algorithim, all the way up to infinity. But no matter how efficient the implementation of an O(n²) algorithm like simple string concatenation with pseudocursors is, it will always eventually lose out to an algorithm of lower complexity order no matter how inefficient it is, like FOR XML string concatenation, which is a very inefficient O(n).

So what big-O notation tells us is that while I might be able to tune a Square algorithim to beat a Triangular one because they are both O(n²), I will never be able to tune a Triangular algorithm (O(n²) )to beat a Linear one (O(n)). Except at the low end where it's less important anyway.