Googmeister wrote: > > Hi Gm, > > > > If finding this interval requires linear time, then the run time is > > proprtional to n^2 > > No. It's the standard n log n recurrence. > > > because there is no bound on the size of the > > interval you're searching for > > Yes there is. At each recursive call the size of the interval > shrinks by a factor of 2. Once you've divide the interval, > you no longer need to worry about intervals crossing > the border. > > > and each of n elements must eventually > > become a[m] > > That's true. But the size of the interval left to examine > will be 1 or 2 for most of them.
I see. Nice. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
