Question

Can I get a breakdown line by line of the time complexity, I know it is O(NlogN) but I am trying to better understand time complexity as a whole.

Input :- N , Array[N]

                               function findSmallestPair()

                               sort the Array

                               int minimumDiff := INFINITY , A := -1 , B := -1;  

                               for(int i : 1 to N-1)

                               begin for

               currentDiff = Array[i]-Array[i-1]

               if(currentDiff < minimumDiff)

               begin if

                              A := Array[i-1];

                              B := Array[i];

                              minimumDiff = currentDiff;

                   end if

              end for

           return {A,B}; end function                      

Answer 1

Time Complexity:

function findSmallestPair()

                               sort the Array //Using standard sort method generally it takes O(nlogn) time(eg:Merge Sort)

                               int minimumDiff := INFINITY , A := -1 , B := -1; //Constant Operation O(1) time

                               for(int i : 1 to N-1) //Loop iterate from1 to n-1 ,So Time complexity O(n)

                               begin for

               currentDiff = Array[i]-Array[i-1] // Constant Operation O(1) time

               if(currentDiff < minimumDiff) //If also take constant operation time O(1)

               begin if

                              A := Array[i-1]; //O(1)

                              B := Array[i]; //O(1)

                              minimumDiff = currentDiff; //O(1)

                   end if

              end for

           return {A,B}; end function                     

So we can easily find that the maximum time complexity is O(nogn) .

If the sort line is removed from your code then the time complexity is O(n).