Arunachalam wrote: > Hi, > can you please elaborate on your question? > > If I understand you correct then you are given an array of Length 2n with > elements a1,a2...an,b1,b2.. bn. > > Now you are asked to modify the array to a1,b1,a2,b2.....an,bn. > > If this is the problem then the solution is straight forward. For each > element not in place try to find its destination.
Unless 'try to find its destination' is O(1), you just exceeded O(n) for the set. > Make a backup of the > destination and then put this element there and mark the current location as > empty. Now Keep on doing this until the destination reaches an empty place. > When destination reaches empty place restart the process. This means that you will restart the process (n/2) - 1 times (if you take care to end when everything is in place). Assuming that, on average, a search covers n/2 elements you now have a run time of (n/2)^2 - (n/2) or O(n^2) > > This is of O(n) Since at the first time itself the element will be moved to > its place. And for the element in its place we will not do any processing. > So this is clearly of order n. > > If this is not your question then please do state your question clearly. > > regards > Arunachalam. > > > On 7/6/06, subrahmanyam kambala <[EMAIL PROTECTED]> wrote: > > > > array contains 2n numbers like a1a2a3a4a5...anb1b2b3...bn > > > > i want the array in such a way that a1b1a2b2a3b3.....anbn > > > > in O(n) time complexity and O(1) space complexity.. > > i got with O(nlogn) complexity... > > > > is it possible ? > > > > > > > > > > > > > -- > =================================== > want to know more about me > http"//ww.livejournal.com/users/arunachalam > > ------=_Part_18306_27764055.1152170119168 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 1648 > > <div>Hi,</div> > <div> can you please elaborate on your question?</div> > <div> </div> > <div>If I understand you correct then you are given an array of Length 2n > with elements a1,a2...an,b1,b2.. bn.</div> > <div> </div> > <div>Now you are asked to modify the array to a1,b1,a2,b2.....an,bn. </div> > <div> </div> > <div>If this is the problem then the solution is straight forward. For each > element not in place try to find its destination. Make a backup of the > destination and then put this element there and mark the current location as > empty. Now Keep on doing this until the destination reaches an empty place. > When destination reaches empty place restart the process. > </div> > <div> </div> > <div>This is of O(n) Since at the first time itself the element will be moved > to its place. And for the element in its place we will not do any processing. > So this is clearly of order n.</div> > <div> </div> > <div>If this is not your question then please do state your question > clearly.</div> > <div> </div> > <div>regards</div> > <div>Arunachalam.<br><br> </div> > <div><span class="gmail_quote">On 7/6/06, <b > class="gmail_sendername">subrahmanyam kambala</b> <<a href="mailto:[EMAIL > PROTECTED]">[EMAIL PROTECTED]</a>> wrote:</span> > <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px > 0.8ex; BORDER-LEFT: #ccc 1px solid"> > <div>array contains 2n numbers like a1a2a3a4a5...anb1b2b3...bn<br><br>i want > the array in such a way that a1b1a2b2a3b3.....anbn<br><br>in O(n) time > complexity and O(1) space complexity..<br>i got with O(nlogn) complexity... > <br><br>is it possible ?<br><br> > ------=_Part_18306_27764055.1152170119168-- --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
