On 3/14/07, NUPUL <[EMAIL PROTECTED]> wrote: > > Firstly your problem is not out of the blue...it's an enquiry for an > existence of such an algorithm. Secondly, a good deal of research has > gone into finding algorithms with O(n) sorting time and that too > inplace (with space of O(1)). This is an ideal requirement! Existing
I think this problem is a sort of brain teaser that the problem setter has come up with and would like to share on this forum. So yes, for all practical purposes this problem is _out of the blue_. Second, under the comparison model of computation, the O(n log n) lower bound for the generic sorting problem has been long proven. The very famous "Introduction to Algorithms : CLRS" which you seem to quote in every second sentence carries a proof of the same. > > requirement or just curiosity? Anyways, I don't think such an > algorithm exists...keep reading texts and do correct me if I'm wrong. Don't think it exists?! Wow.. That's nice, might want to back that up with some theory. > > Try looking at threaded binary trees. > WHY?! In his previous post the problem setter did mention a way out! And IMHO threaded binary trees really can't be called O(1) space, so why then go for it? > > A hint for what? Is this your second algo? different from the above? > Then why give a hint and not the complete solution algorithmically > A hint to arrive at the solution! Duh! And why not give the complete solution? Cos the fun is in _solving_ not reading the solution. -- Regards, Rajiv Mathews --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
