@Ravindra: Can you explain the algorithm for step 3 in more detail? I don't yet see how you do it in O(n^2), since it seems to me that comparing one A[i,j] to all the A[j,k] is already O(n^2). What am I missing?
Dave On Oct 24, 12:05 am, ravindra patel <[email protected]> wrote: > Can be done in O(n^2) time using the slope as people suggested above. > > 1- Sort the points in increasing order of x cord. O(nlogn) > 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - > O(n^2) [Note that point i and j are sorted in increasing order of x] > 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in O(n^2)] > > Thanks, > - Ravindra > > > > On Sun, Oct 24, 2010 at 10:11 AM, Dave <[email protected]> wrote: > > @Preetika: Then you have to look for duplicates in an array of n(n-1)/ > > 2 real numbers. I think this takes the complexity above O(n^2). > > > Dave > > > On Oct 23, 10:54 pm, preetika tyagi <[email protected]> wrote: > > > You have to scan every pair of points only once to get the value of 'm' > > and > > > 'a', so the time complexity would be O(n^2). > > > > On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan <[email protected]> > > wrote: > > > > there are (n*(n-1))/2pairs of points. I think if we use your method, > > the > > > > time complexity should be O(n^4). > > > > > Is it possible to put all points into k different domain and using > > > > T(n)=T(n/k)+f(n) to solve this problem? > > > > > On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi < > > [email protected]>wrote: > > > > >> Is there any specific need to use recursion? > > > > >> One alternate is to find slope and constant (m and c) for every pair > > of > > > >> points and same value of m & c will specify the points on the same > > line. > > > >> Time complexity is O(n*n). > > > > >> On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan <[email protected] > > >wrote: > > > > >>> Given n point on the plane, find out whether any 3point on the same > > > >>> line. > > > > >>> How to use recursion to solve the problem? Could you help me find the > > > >>> algorithm and give the time complexity? > > > > >>> Bests, > > > >>> Claire > > > > >>> -- > > > >>> You received this message because you are subscribed to the Google > > Groups > > > >>> "Algorithm Geeks" group. > > > >>> To post to this group, send email to [email protected]. > > > >>> To unsubscribe from this group, send email to > > > >>> [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > > <algogeeks%2bunsubscr...@googlegroups.com> > > > >>> . > > > >>> For more options, visit this group at > > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > > >> -- > > > >> You received this message because you are subscribed to the Google > > Groups > > > >> "Algorithm Geeks" group. > > > >> To post to this group, send email to [email protected]. > > > >> To unsubscribe from this group, send email to > > > >> [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > > <algogeeks%2bunsubscr...@googlegroups.com> > > > >> . > > > >> For more options, visit this group at > > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > > <algogeeks%2bunsubscr...@googlegroups.com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
