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 < [email protected]> 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 [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.
