@Asquare: You've got it! Each for loop runs n times, and within the first for loop, the sum of the number of times the while loop runs is at most n, because it only loops for numbers that are in the wrong spot and every iteration puts another number in the right spot, so after at most n iterations, every number is in the right spot (except the duplicates). E.g., on the input 2,3,4,5,1,2,3, the while loop iterates 5 times while i = 1 to produce the array 1,2,3,4,5,2,3, and then does not iterate at all for the remaining 6 values of i. Thus, the algorithm is O(n).
Dave On Oct 12, 1:43 pm, Asquare <anshika.sp...@gmail.com> wrote: > @Dave - > I have a doubt.. > will we not incorporate the complexity we get for each while loop > within the for loop..?? > Basically complexity 2n right..?? > another n because while loop runs for each misplaced number.. right?? > which we take as O(n).. Have I understood it the right way?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
