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(N2/2). That's much easier to compare to a cartesian join which is both N2 and O(n2) 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(n2). Thus the complexity of all square and all triangular algorithms have the same order.
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]