Log in  ::  Register  ::  Not logged in

 Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 O(n) , O(n log n), O(n^2) Rate Topic Display Mode Topic Options
Author
 Message
 Posted Tuesday, June 9, 2009 4:31 AM
 SSCrazy Group: General Forum Members Last Login: 2 days ago @ 10:01 PM Points: 2,043, Visits: 2,581
 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 Group: General Forum Members Last Login: Friday, November 18, 2016 2:58 AM Points: 1,334, Visits: 1,466
 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 graphO(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 nI 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 Group: General Forum Members Last Login: Yesterday @ 6:24 AM Points: 23,522, Visits: 37,765
 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.
Post #731410
 Posted Tuesday, June 9, 2009 7:27 AM
 SSC-Forever Group: General Forum Members Last Login: Saturday, December 3, 2016 5:18 AM Points: 45,619, Visits: 44,147
 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 ShawMicrosoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild: Discussions on DB performance with occasional diversions into recoverabilityWe walk in the dark places no others will enterWe stand on the bridge and no one may pass
Post #731428
 Posted Tuesday, June 9, 2009 10:50 AM
 SSCrazy Eights Group: General Forum Members Last Login: Tuesday, October 25, 2016 7:17 AM Points: 9,298, Visits: 9,517
 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 mystringstep 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 formulaN = 5...5^2 = 5*5 = 2525+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: @RBarryYoungProactive Performance Solutions, Inc. "Performance is our middle name."
Post #731657
 Posted Tuesday, June 9, 2009 11:02 AM
 SSCrazy Eights Group: General Forum Members Last Login: Tuesday, October 25, 2016 7:17 AM Points: 9,298, Visits: 9,517
 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: @RBarryYoungProactive Performance Solutions, Inc. "Performance is our middle name."
Post #731679
 Posted Tuesday, June 9, 2009 11:12 AM
 SSCrazy Eights Group: General Forum Members Last Login: Tuesday, October 25, 2016 7:17 AM Points: 9,298, Visits: 9,517
 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: @RBarryYoungProactive Performance Solutions, Inc. "Performance is our middle name."
Post #731693
 Posted Tuesday, June 9, 2009 1:27 PM
 SSCrazy Group: General Forum Members Last Login: 2 days ago @ 10:01 PM Points: 2,043, Visits: 2,581
 Declare @str varchar(5)select @str = ''select @str = @str + no from mystringstep 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 formulaN = 5...5^2 = 5*5 = 2525+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 is1) Time to concatenate the string2) Space claimed by the variables3) Resource taken to do the above two operation karthik
Post #731817
 Posted Tuesday, June 9, 2009 1:52 PM
 SSChampion Group: General Forum Members Last Login: Monday, August 29, 2016 1:09 PM Points: 13,999, Visits: 9,728
 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, ETCProperty 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 Group: General Forum Members Last Login: 2 days ago @ 10:01 PM Points: 2,043, Visits: 2,581
 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

 Permissions

 Copyright © 2002-2016 Redgate. All Rights Reserved. Privacy Policy. Terms of Use. Report Abuse.