Group: General Forum Members Last Login: Wednesday, March 19, 2014 1:43 AM Points: 2,020,Visits: 2,515

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 :)

Group: General Forum Members Last Login: 2 days ago @ 2:08 AM Points: 1,269,Visits: 1,400

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.

Group: General Forum Members Last Login: Today @ 7:50 PM Points: 22,504,Visits: 30,218

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.

Group: General Forum Members Last Login: Today @ 11:52 AM Points: 41,530,Visits: 34,446

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

Group: General Forum Members Last Login: Friday, March 28, 2014 2:25 PM Points: 9,902,Visits: 9,479

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.

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.

Group: General Forum Members Last Login: Friday, March 28, 2014 2:25 PM Points: 9,902,Visits: 9,479

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.

Group: General Forum Members Last Login: Friday, March 28, 2014 2:25 PM Points: 9,902,Visits: 9,479

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.

Group: General Forum Members Last Login: Wednesday, March 19, 2014 1:43 AM Points: 2,020,Visits: 2,515

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.

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.