0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Quote:
Originally Posted by SaswatPadhi View Post
CrazyGal is right, it's O(n^2), but it would be better to say it's O(n*m).
No, because O syntax doesn't work that way. O(n^2) is correct, because if all lengths are set to n and n increases, the time for the algorithm increases along the line n*n. So if n increases from 4 to 5 to 6, then the time increases according to a y=x^2 relationship from 16 to 25 to 36.

The "histogram" algorithm is O(n) even though there are 2 parses and you might think it's O(2n), but again that's misunderstanding what the O syntax is designed for. As n increases, the time for the algorithm only increases linearly, e.g. if n increases by 5% then the overall time increases by 5%.

Quote:
You see the use of strchr(), which searches for a character inside string b. It performs 'm' operations : matches the character with each char of string b.
As strchr() is executed in each iteration of the "while" loop, total number of operations is n*m.
Correct, and that's why it's O(n^2).

See http://en.wikipedia.org/wiki/Big_O_notation for more information than you ever wanted to know about Big O notation.
0
SaswatPadhi's Avatar, Join Date: May 2009
~ Б0ЯИ Τ0 С0δЭ ~
Quote:
Originally Posted by xpi0t0s View Post
No, because O syntax doesn't work that way. O(n^2) is correct, because if all lengths are set to n and n increases, the time for the algorithm increases along the line n*n. So if n increases from 4 to 5 to 6, then the time increases according to a y=x^2 relationship from 16 to 25 to 36.
I don't agree.
O(n^2) is applicable when there is one parameter(n) that affects the time complexity of your algo. But, when there are more than one variable say m,n,p .. you can't say O(mnp) = O(n^3). ( See the complexity of (m x n)*(n x p) matrix multiplication : Complexity of matrix algebra(Wikipedia) )

Tina's algorithm has two parameters : m, n which represent lengths of A and B respectively. So, the time complexity should be O(mn). And, I know O(mn) algos exist. You can just google "O(mn) algorithm".

O(mn) = O(n) if m is constant.
O(mn) = O(n^2) if m == n and m is not an independent variable

Quote:
Originally Posted by xpi0t0s View Post
The "histogram" algorithm is O(n) even though there are 2 parses and you might think it's O(2n), but again that's misunderstanding what the O syntax is designed for. As n increases, the time for the algorithm only increases linearly, e.g. if n increases by 5% then the overall time increases by 5%.
I mentioned in my post, that it's O(m+n).
Now, the explanation above justifies that.

Quote:
Originally Posted by xpi0t0s View Post
Correct, and that's why it's O(n^2).

See http://en.wikipedia.org/wiki/Big_O_notation for more information than you ever wanted to know about Big O notation.
I saw the link and found something related at : Multiple Variables.
Please go through.

PS: Please go through the attached PDF as well. It deals exclusively with multiple variables.
Attached Files
File Type: pdf asymptotic.pdf (149.9 KB, 4 views)
0
SaswatPadhi's Avatar, Join Date: May 2009
~ Б0ЯИ Τ0 С0δЭ ~
Still waiting for your reply, xpi0t0s.
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Quote:
Originally Posted by SaswatPadhi View Post
Still waiting for your reply, xpi0t0s.
Sorry, didn't know one was expected.
Yep, I was wrong, you were right, I bow to your superior intellect.
0
SaswatPadhi's Avatar, Join Date: May 2009
~ Б0ЯИ Τ0 С0δЭ ~
Now, that sounds sarcastic.
You are the mentor here.

It's not about intellect. I didn't develop some path breaking algo or something -- I just wrote what I had understood from the theories.

I have just passed my 12th grade. I expected a reply from your side, because we (me, mayjune and many others here) consider you much more experienced in programming, than we people. I just wanted to be sure that what I have understood was not a misunderstanding. There are many things in C++ that I didn't know (or misunderstood) and you have clarified them beautifully.

So, don't take that -vely. I didn't want to hear from you that I am right and you are wrong.
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
OK fair enough. I was operating on the basis of guesswork, some basic knowledge of O(x) syntax and a quick look at the Wiki article, so I thought O(m*n) didn't exist and was equivalent to O(n^2). I shouldn't really try to talk authoritatively on a subject I don't really know.
0
mayjune's Avatar, Join Date: Jun 2009
Invasive contributor
its ok xpi0t0s, one mistake out of 10000000 is allowed, since i have never seen you making any mistakes before