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.
[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]