Log in
::
Register
::
Not logged in
Home
Tags
Articles
Editorials
Stairways
Forums
Scripts
Videos
Blogs
QotD
Books
Ask SSC
SQL Jobs
Training
Authors
About us
Contact us
Newsletters
Write for us
Recent Posts
Recent Posts
Popular Topics
Popular Topics
Home
Search
Members
Calendar
Who's On
Home
»
SQL Server 7,2000
»
TSQL
»
O(n) , O(n log n), O(n^2)
42 posts, Page 4 of 5
««
«
1
2
3
4
5
»»
O(n) , O(n log n), O(n^2)
Rate Topic
Display Mode
Topic Options
Author
Message
Jeff Moden
Jeff Moden
Posted Wednesday, June 10, 2009 5:52 AM
SSCDedicated
Group: General Forum Members
Last Login: Yesterday @ 8:47 PM
Points: 37,077,
Visits: 33,943
RBarryYoung (6/9/2009)
Jeff Moden (6/9/2009)
O(wtf
^{2}
)
Heh. Hey, I'm not the one who asked the question, I'm just trying to answer them.
Oh no... sorry, Barry. Wasn't directed at anyone in particular.
Shifting gears,
If someone asked me to define it so that a layman could understand it, I'd tell them the "O" is an abbreviation for "Order of Magnitude" and the the formula it contains is nothing more than the part of another formula that's going to have the biggest effect on things... that's it's just shorthand to make comparing some more complex formulas easier to compare as a swag (order of magnitude).
For example, the forumula for the number of rows that a triangular join will touch in SQL Server is ((N
^{2}
+N)/2)+N. 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}
/2). That's much easier to compare to a cartesian join which is both N
^{2}
and O(n
^{2}
) to say that a triangular join is approximately half as bad as the square join.
Jeff Moden
"
RBAR
is pronounced "reebar" and is a "Modenism" for "
R
ow
B
y
A
gonizing
R
ow".
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."
(play on words) "Just because you CAN do something in TSQL, doesn't mean you SHOULDN'T."
22 Aug 2013
Helpful Links:
How to post code problems
How to post performance problems
Post #732156
RBarryYoung
RBarryYoung
Posted Wednesday, June 10, 2009 7:35 AM
SSCrazy Eights
Group: General Forum Members
Last Login: Thursday, December 4, 2014 7:52 AM
Points: 9,294,
Visits: 9,495
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}
/2). That's much easier to compare to a cartesian join which is both N
^{2}
and O(n
^{2}
) 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
^{2}
). Thus the complexity of all square and all triangular algorithms have the same order.
 RBarryYoung
,
(302)3750451
blog:
MovingSQL.com
, Twitter:
@RBarryYoung
Proactive
Performance Solutions, Inc.
"Performance is our middle name."
Post #732271
Jeff Moden
Jeff Moden
Posted Friday, June 12, 2009 7:49 PM
SSCDedicated
Group: General Forum Members
Last Login: Yesterday @ 8:47 PM
Points: 37,077,
Visits: 33,943
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}
/2). That's much easier to compare to a cartesian join which is both N
^{2}
and O(n
^{2}
) 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
^{2}
). 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 "reebar" and is a "Modenism" for "
R
ow
B
y
A
gonizing
R
ow".
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."
(play on words) "Just because you CAN do something in TSQL, doesn't mean you SHOULDN'T."
22 Aug 2013
Helpful Links:
How to post code problems
How to post performance problems
Post #734219
RBarryYoung
RBarryYoung
Posted Saturday, June 13, 2009 11:32 AM
SSCrazy Eights
Group: General Forum Members
Last Login: Thursday, December 4, 2014 7:52 AM
Points: 9,294,
Visits: 9,495
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}
/2). That's much easier to compare to a cartesian join which is both N
^{2}
and O(n
^{2}
) 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
^{2}
). 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 bigO 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
^{2}
) 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 bigO 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
^{2}
), I will never be able to tune a Triangular algorithm (O(n
^{2}
) )to beat a Linear one (O(n)). Except at the low end where it's less important anyway.
 RBarryYoung
,
(302)3750451
blog:
MovingSQL.com
, Twitter:
@RBarryYoung
Proactive
Performance Solutions, Inc.
"Performance is our middle name."
Post #734394
Jeff Moden
Jeff Moden
Posted Saturday, June 13, 2009 11:58 AM
SSCDedicated
Group: General Forum Members
Last Login: Yesterday @ 8:47 PM
Points: 37,077,
Visits: 33,943
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}
/2). That's much easier to compare to a cartesian join which is both N
^{2}
and O(n
^{2}
) 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
^{2}
). 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 bigO 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
^{2}
) 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 bigO 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
^{2}
), I will never be able to tune a Triangular algorithm (O(n
^{2}
) )to beat a Linear one (O(n)). Except at the low end where it's less important anyway.
You're absolutely correct and preaching to the choir. I should have just said that it was O(n
^{2}
) and left it at that because that would have been the correct thing to do.
Still, a triangular join will beat a square join by a factor of two every time.
Jeff Moden
"
RBAR
is pronounced "reebar" and is a "Modenism" for "
R
ow
B
y
A
gonizing
R
ow".
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."
(play on words) "Just because you CAN do something in TSQL, doesn't mean you SHOULDN'T."
22 Aug 2013
Helpful Links:
How to post code problems
How to post performance problems
Post #734400
RBarryYoung
RBarryYoung
Posted Saturday, June 13, 2009 12:32 PM
SSCrazy Eights
Group: General Forum Members
Last Login: Thursday, December 4, 2014 7:52 AM
Points: 9,294,
Visits: 9,495
Jeff Moden (6/13/2009)
You're absolutely correct and preaching to the choir. I should have just said that it was O(n
^{2}
) and left it at that because that would have been the correct thing to do.
Still, a triangular join will beat a square join by a factor of two every time.
Heh. Thanks, now I have to spend the rest of the day coming up with a countexample?
 RBarryYoung
,
(302)3750451
blog:
MovingSQL.com
, Twitter:
@RBarryYoung
Proactive
Performance Solutions, Inc.
"Performance is our middle name."
Post #734415
karthik M
karthik M
Posted Friday, September 28, 2012 9:57 PM
SSCrazy
Group: General Forum Members
Last Login: Wednesday, April 1, 2015 12:50 AM
Points: 2,034,
Visits: 2,553
Experts,
is there any solution available for "Mass concatenate" in SQL 2008 OR SQL 2012?
karthik
Post #1366159
TomThomson
TomThomson
Posted Saturday, September 29, 2012 9:41 AM
SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 11:04 PM
Points: 8,309,
Visits: 10,023
GilaMonster (6/8/2009)
karthikeyan (6/8/2009)
1) O(n) means ?
2) O(n^2) means ?
3) O(n log n) means ?
Surely you covered the Big O notation for algorithmic (time) complexity at university? It's a fundamental of Comp Sci theory.
Try these
http://en.wikipedia.org/wiki/Computational_complexity_theory
http://en.wikipedia.org/wiki/Big_O_notation
It's not often I disagree with Gail, but here I have to say that those references probably are not useful.
The first is off into esoteric stuff way beyond the level of a simple primer, going so far as to talk about open problems, and surely anything that far beyond primer level is unlikely to be helpful to someone asking this question. The second gives a formal definition which makes it correct to say that the constant function C1(x) = 1 is O(exp(exp(exp(x)))), and the identity function I(x) = x is O(x^x), which certainly is not going to give someone who wants to know what we mean by it anything like the right idea.
So I'm going to offer a description for laymen:
suppose we have an algorithm A which given n rows of input (or count rows of output instead, if that is useful) will on average have to do W(n) units of work and use S(n) amount of store. Then we say W(n) is O(n) if (for big enough n) when n doubles then W(n) roughly doubles. We say W(n) is O(n^2) if (for big enough n) when n doubles W(n) goes up by roughly a factor of 4 (2 = 2^2) and when n goes up by a factor of 10 W(n) goes up roughly by a factor of 100. Work complexity W(n) is O(n) means the amount of work is roughly proportional to n, work complexity W(n) is O(n^2) means the amount of work is roughly proportional to n^2. The same for any other function in the brackets after the big O: if the work complexity is O(n log(n)) then for big enough the amount of work is roughly proportional to n*log(n), if the work complexity is O(2^n) each extra row roughly doubles the amount of work, and so on. The idea of Space complexity S(n) being O(g(n)) for some function g is much the same.
Obviously a formal mathematical definition is a bit different, but for practical purposes when working with database stuff the description above is what is actually needed. Of course you won't solve any of the currently unresolved mathematical issues in complexity theory with that description, but that's not what (most) database people want to do.
edit: woops, just noticed that this thread started a very long time ago, and my comments are on a very early post, not on today's post, so may no longer be of any interest.
Tom
Post #1366198
TomThomson
TomThomson
Posted Saturday, September 29, 2012 9:52 AM
SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 11:04 PM
Points: 8,309,
Visits: 10,023
karthikeyan444867 (9/28/2012)
Experts,
is there any solution available for "Mass concatenate" in SQL 2008 OR SQL 2012?
People have already referred to teh "for xml" method, which is O(n) so for larg enough n withh be much better than the other methods discussed (which are all O(n^2)).
Tom
Post #1366200
karthik M
karthik M
Posted Saturday, March 16, 2013 9:59 AM
SSCrazy
Group: General Forum Members
Last Login: Wednesday, April 1, 2015 12:50 AM
Points: 2,034,
Visits: 2,553
Hello All,
I just refreshed all my posts.
This is a very old post (asked on 2009) :)
How to identify whether a code fall under O(n) / O (n2) / O(n log n) by seeing the code ?
karthik
Post #1431907
« Prev Topic

Next Topic »
42 posts, Page 4 of 5
««
«
1
2
3
4
5
»»
Permissions
You
cannot
post new topics.
You
cannot
post topic replies.
You
cannot
post new polls.
You
cannot
post replies to polls.
You
cannot
edit your own topics.
You
cannot
delete your own topics.
You
cannot
edit other topics.
You
cannot
delete other topics.
You
cannot
edit your own posts.
You
cannot
edit other posts.
You
cannot
delete your own posts.
You
cannot
delete other posts.
You
cannot
post events.
You
cannot
edit your own events.
You
cannot
edit other events.
You
cannot
delete your own events.
You
cannot
delete other events.
You
cannot
send private messages.
You
cannot
send emails.
You
may
read topics.
You
cannot
rate topics.
You
cannot
vote within polls.
You
cannot
upload attachments.
You
may
download attachments.
You
cannot
post HTML code.
You
cannot
edit HTML code.
You
cannot
post IFCode.
You
cannot
post JavaScript.
You
cannot
post EmotIcons.
You
cannot
post or upload images.
Copyright © 20022015 Simple Talk Publishing. All Rights Reserved.
Privacy Policy.
Terms of Use.
Report Abuse.