@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> > >>> . > >>> 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> > >> . > >> 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> > > . > > 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.
