Selection Sort Recurrence Relation

Question

up front this is a homework question but I am having a difficult time understanding recurrence relations. I've scoured the internet for examples and they are very vague to me. I understand that recurrence relations for recursive algorithms don't have a set way of handling each one but I am lost at how to understand these. Here's the algorithm I have to work with:

void selectionSort(int array[]) {
   sort(array, 0); 
} 

void sort(int[] array, int i) {
   if (i < array.length - 1) 
   { 
      int j = smallest(array, i);    T(n) 
      int temp = array[i]; 
      array[i] = array[j]; 
      array[j] = temp; 
      sort(array, i + 1);    T(n)
   } 
} 

int smallest(int[] array, int j)     T(n - k)
{ 
   if (j == array.length - 1) 
      return array.length - 1; 
   int k = smallest(array, j + 1); 
   return array[j] < array[k] ? j : k; 
}

So from what I understand this is what I'm coming up with: T(n) = T(n – 1) +cn + c The T(n-1) represents the recursive function of sort and the added cn represents the recursive function of smallest which should decrease as n decreases since it's called only the amount of times that are remaining in the array each time. The constant multiplied by n is the amount of time to run the additional code in smallest and the additional constant is the amount of time to run the additional code in sort. Is this right? Am I completely off? Am I not explaining it correctly? Also the next step is to create a recursion tree out of this but I don't see this equation as the form T(n) = aT(n/b) + c which is the form needed for the tree if I understand this right. Also I don't see how my recurrence relation would get to n^2 if it is correct. This is my first post too so I apologize if I did something incorrect here. Thanks for the help!

Answer 1

The easiest way to compute the time complexity is to model the time complexity of each function with a separate recurrence relation.

We can model the time complexity of the function smallest with the recurrence relation S(n) = S(n-1)+O(1), S(1)=O(1). This obviously solves to S(n)=O(n).

We can model the time complexity of the sort function with T(n) = T(n-1) + S(n) + O(1), T(1)=O(1). The S(n) term comes in because we call smallest within the function sort. Because we know that S(n)=O(n) we can write T(n) = T(n-1) + O(n), and writing out the recurrence we get T(n)=O(n)+O(n-1)+...+O(1)=O(n^2).

So the total running time is O(n^2), as expected.