Young's Tableau.. go along non-major diagonal in a stair up or down fashion
On Fri, Jul 2, 2010 at 11:46 PM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > @Rahul: the worst case running time for your algo is O(nlogn) > > but here's another approach: > suppose we're searching for x > binary search on the diameter of the matrix (note that the diameter is > sorted) > if x is not on the diameter > when you find i such that a[i][i]<x<a[i+1][i+1] > split the matrix to four matrices > > ----------------- > | R1 | R2 | > |----------------- > | R3 | R4 | > ----------------- > > x cannot be in R1 since it's biggest element is a[i][i] which is less than > x > and it can't be in R4 since it's least element is a[i+1][i+1] which is > bigger than x > so we search recursively in R3 and R2 > in avg case since the avg size of R3 and R2 is n/2 * n/2 > T(n) = 2T(n/2) + O(lgn) > using the master method the running time is O(n) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@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 algoge...@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.
