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%[email protected]> > <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%[email protected]> > <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%[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]<algogeeks%[email protected]> > . > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
