RE: O(n) , O(n log n), O(n^2)

SSC Guru

Points: 1003875

June 12, 2009 at 7:49 pm

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. 😛

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)