Is there a simple way to find the time complexity?

Question

Our teacher didn't taught us how to analyze the running time of an algorithm before she want us to report about Shell sort.

I just want to know if there is a simple way to find the average/best/worst case performance of an algorithm like shell sort.

//for references

class ShellSort{
  void shellSort(int array[], int n){
    //n = array.length
    for (int gap = n/2; gap > 0; gap /= 2){
      for (int i = gap; i < n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
    }
  }

Answer 1

welcome to stack overflow! Usually, time complexity for a sorting algorithm is measured via the number of key comparisons performed. One can begin by considering what is the input that requires the fewest number of key comparisons to completely sort (best case) then follow it up with the input that would require the most number (worst case). Oftentimes, the best case would be a sorted list and the worst case might be a list sorted in reverse order, though this might not be the case for some divide and conquer algorithms.

As for average case, once you derive the best and worst case, you know the average is bounded between the two. If both have the same time complexity class (oftentimes 'Big Oh' class), then you know the average is the same. Otherwise you can derive it mathematically through a probabilistic analysis.

For every loop over the array, that would add a time complexity factor of 'n', and nested loops would 'multiply' this complexity. i.e. 2 nested loops give a complexity of n^2 and 3 nested loops give a complexity of n^3.

Partitioning an array into half repeatedly would often give you a time complexity factor of 'log(n)'.