@Yogi: Your algo (though it seems N^2) is actually N^3.
According to your algorithm, you need to have a loop to select the starting
value of the common difference of the AP.
As per what you've written, an implementation is:
for all distinct d values in the diff matrix { // O(N^2) loop
Let location of d value be (i, j)
length = 2;
repeat:
for k in range (j...N-1) { // O(N) loop
if(diff[j][k] == d) {
length++;
j = k;
goto repeat;
}
}
}
The time complexity of this solution is O(number of distinct d values x
(length of sequence - 1) x N).
For the case that all the diff values are distinct, the time complexity of
this solution is O(N^3) (since length of sequence will be 2)
Please let me know if you have a way to implement this faster than O(N^3) or
an alteration of the algorithm that brings down the complexity to O(N^2).
Alternatively, if you believe that this algo is O(N^2), could you please
provide a complexity analysis supporting that?
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/pKqqgqKxFzIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
