If cycles are present then how will u say that it O ( N ) + O ( N / 2 ) I think it is O ( N * N ) = O ( N ^ 2 ) , becuase we have to start scanning from the first and the next misplaced A position......
One possible solution is that - arrange the array as A1, B1, A3, B3, A5,B5,...........,A2,B2,A4,B4........ To do this it takes O ( n ) time, Now use any sorting algo. treating that A1, B1 as a single element, It seems like sorting of 1,3,5,7....2,4,6,......., which takes O ( n log n ) So overall complexity is O ( n log n ) --~--~---------~--~----~------------~-------~--~----~ 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-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
