Search code examples
performancetime-complexitycomplexity-theory

What is the asymptotic runtime complexity of my code?


Heres my code below, i'm trying to find out the asymptotic runtime complexity of my code but im not sure

public static int myAlgorithm(List<Integer> myList) {
 if (myList.isEmpty()) {
 return 0;
    } 
 
Collections.sort(myList); // Can assume the sort algorithm is merge sort 

int sum = 0; 
int max = myList.get(myList.size() - 1); 
for (int item : myList) {
 int diff = Math.abs(max - item);
 sum = sum + diff; 
    } 
return sum; 
} 

Solution

  • Assuming that the sort you're using is merge sort, the asymptomatic running time of the algorithm is O(NlogN)

    The most complex step is the sort step.

    The code after that is approximately O(N); 1 loop and 1 passthrough when looking for max.