Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««12345»»»

O(n) , O(n log n), O(n^2) Expand / Collapse
Author
Message
Posted Tuesday, June 9, 2009 4:31 AM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 30, 2014 8:23 AM
Points: 2,025, Visits: 2,521
Gail,

i expected this question from you. Since i studied these concepts just to pass the exams, beacuse that time i don't know the real time usage and it will be used in our programming skill, I forgot the concepts.

Once i got the job, then only i realized that all i studied will be applied in the work...anyway hereafter i never forgot this chapters.:)..Thanks for teaching me....Thank you Gail :)


karthik
Post #731302
Posted Tuesday, June 9, 2009 4:38 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Sunday, August 3, 2014 3:41 PM
Points: 1,219, Visits: 1,430
Hi
I'm sure Barry & Gail will give full answers, but this interpretation may help.

Don't think of O(n) / O(n^2) as proper mathematical formulas that can be solved. Think of them as a convenient shorthand description for a problem type.

So O(n) describes a linear problem - as n increases, the solution increases proportionally to n as in a straight line graph

O(n^2) is essentially a quadratic problem - as n increases, the solution increases proportionally to n-squared - or some function of n-squared.

O(log n) means the solution increase proportional to log n

I may be totally wrong or this could be too simplistic, but thats what I understood from the Wiki article and various other researching.

Post #731305
Posted Tuesday, June 9, 2009 7:12 AM


SSC-Insane

SSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-InsaneSSC-Insane

Group: General Forum Members
Last Login: Today @ 11:15 AM
Points: 20,682, Visits: 32,283
karthikeyan (6/9/2009)
Gail,

i expected this question from you. Since i studied these concepts just to pass the exams, beacuse that time i don't know the real time usage and it will be used in our programming skill, I forgot the concepts.

Once i got the job, then only i realized that all i studied will be applied in the work...anyway hereafter i never forgot this chapters.:)..Thanks for teaching me....Thank you Gail :)


I have an idea, how about actually answering Gail's questions about where and when you went to school for your MCA and BS degrees instead of just this fluff.




Lynn Pettis

For better assistance in answering your questions, click here
For tips to get better help with Performance Problems, click here
For Running Totals and its variations, click here or when working with partitioned tables
For more about Tally Tables, click here
For more about Cross Tabs and Pivots, click here and here
Managing Transaction Logs

SQL Musings from the Desert Fountain Valley SQL (My Mirror Blog)
Post #731410
Posted Tuesday, June 9, 2009 7:27 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 11:10 AM
Points: 39,906, Visits: 36,246
Tom Brown (6/9/2009)
I may be totally wrong or this could be too simplistic, but thats what I understood from the Wiki article and various other researching.


That's pretty much the core of it, yes.

There's a whole tonne of theory as to analysing algorithms to work out their complexity but I don't recall any of the details of that any more. It's way over most people's heads anyway and more for maths/CS researchers.




Gail Shaw
Microsoft Certified Master: SQL Server 2008, MVP
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

Post #731428
Posted Tuesday, June 9, 2009 10:50 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Thursday, June 5, 2014 10:54 AM
Points: 9,294, Visits: 9,480
karthikeyan (6/9/2009)
RBarryyoung and Gail,

Big O notation means the steps to complete a problem. Right?

Sort of. Big-O notation categorizes an algorithm's complexity in terms of the dominant term (without any constant factors) of its execution run-time as a function of the length of its input data("N"), as N approaches infinity. It is a way of talking about the efficiency of an algorithm apart from the efficiency of any particular implementation of that algorithm.

But then you would know that if you had read the Wikipedia articles.

1) what do you mean by O(n^2) problem? Pls don't mistake me if i am asking this question again.

You would know this if you had done what we asked. I will not respond to this question again.

EDIT: fixed formatting mistakes...
2) Big O notation means the steps to complete a problem. we denote it as O(n). But what is the difference between O(n) and O(n^2) ?

This is incorrect. Please read the Wikipedia articles.

Declare @str varchar(5)
select @str = ''
select @str = @str + no from mystring
step 1: '' + '1'
step 2: '1' + '2'
step 3: '12' + '3'
step 4: '123' + '4'
step 5: '1234' + '5'

so if i apply ((N^2) + N)/2 formula

N = 5
...
5^2 = 5*5 = 25
25+5 = 30/2 = 15. Right?

Yes. Now count the total number of characters in quotes in your steps 1 through 5 above, what do you get?

2) Can you explain about the formula you used?


Which formula? I use a lot of them.


{(n)*(n+1)/2} cost of the naive implementation to {n +(n)*(n-1)/(2*k)} where "k" is that percentage. It's better, but it's still O(n^2).

Can you explain it?

It is explained by the text that preceeded it. It is a formula that calculates the execution time of string concatenation that has been improved by being able to use buffer-extension part of the time. "k" is a number between 0 and 1 that expresses how often the buffer-extension trick can be used.


-- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoung
Proactive Performance Solutions, Inc.
"Performance is our middle name."
Post #731657
Posted Tuesday, June 9, 2009 11:02 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Thursday, June 5, 2014 10:54 AM
Points: 9,294, Visits: 9,480
karthikeyan (6/9/2009)
1) SQL Server apparently (based on my tests) already does the "buffer-extension" trick available to mutable strings. Unfortunately, the Extension trick does NOT solve the O(n^2) problem,


If it supports the "buffer-extension" trick,then why it doesn't solve O(n^2) problem. again , i need to know exactly about O(n^2).

Because, as I already explained, it can only be used part of the time.

can you explain it with example? so that i can remember it through my career.

I already did this above, here it is again:
The "buffer-extension trick" is referring to a low-level (Assembler or C) trick that takes advantage of that fact that in most OS's strings often have large gaps of unallocated memory after them. Thus if you want to add the string B$ onto the end of A$, then normally you would have to allocate a new buffer whose length is >= Len(A$) + Len(B$), then copy all of A$ inot it, then copy B$ in after A$ and then re-point A$ to the new buff (and deallocate the old). Besides all of the memory allocation overhead, this is an O(n) operation where n = Len(A$)+Len(B$).

However, if A$ just happens to have an unused portion of memory after it whose size is >= Len(B$) then, instead you can just copy B$ into that unused memory after A$ and extend A$'s length value to inlcude the appended characters.
Please read fully what we have taken the time to write and stop making us repeat ourselves.

Does this issue solved in sql2008?
The "buffer-extension trick" can never solve this problem. It is a trick that can only be used if you are not already using the memory that is immediately above your output string. There is no way that an OS or DB environment can ever guarantee this all of the time. The only true solution is to use a different algorithm.


-- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoung
Proactive Performance Solutions, Inc.
"Performance is our middle name."
Post #731679
Posted Tuesday, June 9, 2009 11:12 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Thursday, June 5, 2014 10:54 AM
Points: 9,294, Visits: 9,480
So we should avoid pseudo cursor. Right?

I never said anything like this.

1) It will be treated as internal cursor. i.e it will perform looping internally.
AFAIK all set processing in SQL Server uses internal cursors. And as long as CPU-cores execute single streams of instructions, all servers, programs and OS's will have to loop internally.
But comparing to external cursor, it will be very fasy. Right?

Yes.

2) is it a good habit to use pseudo cursor in sql programming? if not, what is the workaround for this?
It is a technique. It is not the most desirable technique, but neither is it entirely undesirable. And sometimes it is the best technique available for a problem.


-- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoung
Proactive Performance Solutions, Inc.
"Performance is our middle name."
Post #731693
Posted Tuesday, June 9, 2009 1:27 PM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 30, 2014 8:23 AM
Points: 2,025, Visits: 2,521
Declare @str varchar(5)
select @str = ''
select @str = @str + no from mystring
step 1: '' + '1'
step 2: '1' + '2'
step 3: '12' + '3'
step 4: '123' + '4'
step 5: '1234' + '5'

so if i apply ((N^2) + N)/2 formula

N = 5
...
5^2 = 5*5 = 25
25+5 = 30/2 = 15. Right?




O(n) operation where n = Len(A$)+Len(B$).


so '1' + '2' is an O(n) operation.

O(n^2) problem is
1) Time to concatenate the string
2) Space claimed by the variables
3) Resource taken to do the above two operation



karthik
Post #731817
Posted Tuesday, June 9, 2009 1:52 PM


SSChampion

SSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampionSSChampion

Group: General Forum Members
Last Login: Friday, June 27, 2014 12:43 PM
Points: 13,872, Visits: 9,596
Karthik, '1'+'2' is still O(n^2). What's 1 squared?

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Post #731832
Posted Tuesday, June 9, 2009 1:54 PM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 30, 2014 8:23 AM
Points: 2,025, Visits: 2,521
RBarryYoung (6/8/2009)
karthikeyan (6/8/2009)


[quote]4) What LHS (Left-hand side) function denotes exactly?

Left-hand Functions appear left of the assignment operator ("="):
 Set @str = UPPER('Some text.')

These are normal functions, and AFAIK, in T-SQL, all functions are LHS.

3) What RHS (right-hand side) function denotes exactly?

Right-hand Side functions appear on the right-hand side and they usually do "special" things having to do with addressing the output property or variable. AFAIK, T-SQL does not have any, but in some languages, STUFF is a RHS:
 STUFF(@str, offset, len) = 'foo'

This example would overwrite the output string (@str) with the input string starting at 'offset' for 'len' characters. The difference between this and th LHS STUFF() function in T-SQL is that the RHS version does not return anything, it actually does write over the characters of the @str variable.




3) The "pre-allocate and Stuff" trick popular with mutable strings is not workable in T-SQL because the STUFF() function in T_SQL is NOT like the function of the same name in some general purpose languages: the T-SQL STUFF() is an RHS (right-hand side) function and NOT an LHS (left-hand side) function. AFAIK, there is no function in SQL that can (physically) write into a pre-existing string.


RBarryyoung,

The above two points are confusing me...

you mean to say TSQL STUFF() function can't write into a pre-existing string.



karthik
Post #731834
« Prev Topic | Next Topic »

Add to briefcase ««12345»»»

Permissions Expand / Collapse