Had anyone tried coding this solutions. I have got wrong answer for the implementation. Might be a coding flaw too.
If anyone is able to successfully crack it , please share your solution.
regards
Arunachalam.
On 6/28/06, Gene <[EMAIL PROTECTED]> wrote:
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.
--
===================================
want to know more about me
http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
