On Dec 5, 3:14 pm, Harshith <[email protected]> wrote: > I might be wrong here but, why can't you just sort the block A[i..j] > it will take O((j-i)log(j-i)) (there are many O(n logn) sorting > algorthms) steps and then just look if they are in sequence trivially > another j-i steps.
Don't see what you are getting at. The max-min comparisions to determine if a block is consecutive is O(1), the total steps calculation is due to the number of blocks that need to be checked. > On Dec 3, 1:33 am, Vinoth Kumar <[email protected]> wrote: > > > > > I kinda need the worst case also to be in nlogn. > > Any ideas guys ? > > > -- Vinod > > > On Dec 2, 11:02 pm, Geoffrey Summerhayes <[email protected]> wrote: > > > > On Dec 2, 10:42 am, Geoffrey Summerhayes <[email protected]> wrote: > > > > > It's a binary tree, [ 7 3 4 1 2 6 5 8] has children > > > > [ 7 3 4 1 2 6 5] and [ 3 4 1 2 6 5 8], all the way > > > > down to [ 7 3] [3 4] [4 1] ... > > > > > If you start at the bottom keeping track of min and max > > > > for each node, if max-min == node length - 1 the node > > > > if conseq. then it's just a matter of combining node > > > > together and working up the tree > > > > Darn! > > > > Total steps= n*n/2 - n/2 > > > > Anybody have a math trick? > > > > -- > > > Geoff- 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.
