karthikeyan (6/9/2009)
{(n)*(n+1)/2} cost of the naive implementation to {n +(n)*(n-1)/(2*k)}
how?
{(n)*(n+1)/2} = 15
{n +(n)*(n-1)/(2*k)} = 15
There is no difference.
If K= 0,
=5+(5)*(5-1)/(2*0)
"Divide By Zero error occured".
Right. the problem is that you are quoting my comments on Phil Factor's blog and I could't edit my typos there. Here is a more correct formula:
k*n + (1-k)*(n2 - n)/2
Note that this is still only an approximation because we are waving away the difference between the number of strings and the possibly different lengths of those strings.
How should i determine 'k' value? on what basis i have to determine the value?
I doubt that you could. AFAIK, I am the only person who has ever claimed that K was anything other than 0 (though if I am correct, then there must be folks inside Microsoft who know it also).
but I could get it down to O(n*Log(n)) time which is still a huge improvement
Is it denotes FOR XML option?
or
Is it denotes Pseudo cursor method?
Neither. The naive pseudocursor method is O(n2). The FOR XML method is O(n). I was referring to the very complex modified pseudocursor method that I posted at Phil Factor's blog. It is O(n*log(n)).
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]