Search code examples
time-complexitybig-opseudocode

calculate time complexity for this solution


I have the following code. I think the solution has O(n^2) because it is a nested loop according to the attached image. can anyone confirm?

function sortSmallestToLargest(data):
      sorted_data={}

      while data is not empty:
         smallest_data=data[0]

         foreach i in data:
            if (i < smallest_data):
               smallest_data= i

         sorted_data.add(smallest_data)
         data.remove(smallest_data)

      return sorted_data

reference image


Solution

  • Ok, now I see what you are doing! Yes, you are right, it's O(n²), because you're always looping through every element of data. Your data will decrease by one every loop, but because with O complexity we don't care about constants, we can say it's O(n) for each loop. Multiplying (because one is inside the other) we have O(n²).