tag:blogger.com,1999:blog-4115025577315673827.post7219844306141849497..comments2020-02-26T09:38:33.024+05:30Comments on CSE Blog - quant, math, computer science puzzles: Puzzle on SortingPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-4115025577315673827.post-10828538307362834212010-09-08T17:24:36.285+05:302010-09-08T17:24:36.285+05:30K Q J 10 9 8 7 6 5 4 3 2 1
K 6 5 4 3 2 1 Q J 10 9 ...K Q J 10 9 8 7 6 5 4 3 2 1<br />K 6 5 4 3 2 1 Q J 10 9 8 7<br />1 Q K 6 5 4 3 2 J 10 9 8 7<br />1 2 J Q K 6 5 4 3 10 9 8 7<br />1 2 3 10 J Q K 6 5 4 9 8 7<br />1 2 3 4 9 10 J Q K 6 5 8 7<br />1 2 3 4 5 8 9 10 J Q K 6 7<br />1 2 3 4 5 6 7 8 9 10 J Q K<br /><br /><br />i think this is not np hard either :D<br /><br />m fan of Nikhil Garg myslef niraj <br />joined codechef and written to nikhil pls reply nikhil.Anonymoushttps://www.blogger.com/profile/06444480523751402586noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-26431163313657848902010-08-23T16:35:07.299+05:302010-08-23T16:35:07.299+05:30@Nikhil.. Using the recurrence, all you get is thi...@Nikhil.. Using the recurrence, all you get is this:<br />T(n) <= cn<br /><br />which we already know. I want you to give me an algorithm, where T(n) <= n-1Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5050793454882634342010-08-22T23:57:56.003+05:302010-08-22T23:57:56.003+05:30Why not simply try to follow a divide & conque...Why not simply try to follow a divide & conquer approach ?<br /><br />Move n/2 elements from right to left end & solve these smaller n/2 & ceil(n/2) element sequences . <br /><br />Number of moves :<br /><br />Let T(n) denote number of moves using this algorithm for n numbers. <br />T(1)=0<br />T(n)= T(floor(n/2)) + T(ceil(n/2)) + 1<br /><br />Solving this one can find T(n) & I know this recurrence is not "too" difficult to solve- I have solved it sometime back.<br /><br />PS:As far as proving is concerned this is the best, I think we would be able to come up with an argument which would establish that sorting can be done in time less then O(nlogn). But again, I dont want to think right away.NGhttps://www.blogger.com/profile/00137167173637522039noreply@blogger.com