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