title: Selection Sort Recurrence Relation
body: <p>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:</p>
  
  <pre><code>void selectionSort(int array[]) {
     sort(array, 0); 
  } 
  
  void sort(int[] array, int i) {
     if (i &lt; 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] &lt; array[k] ? j : k; 
  }
  </code></pre>
  
  <p>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!</p>