Explain why T(1) = 0, T(n) = T(n-1) + n-1 aptly describes the number of comparisons for Bubble Sort and then, using the techniques from class (telescoping, master theorem, substitution, etc...), solve the recurrence.

*Please answer both parts of this question!! Also, if you can also explain the following question to me that would be great- If the runtime of Bubble Sort is O(n²), how does this recurrence relation relate to that? Is it because in the Big-Oh analysis it's number of comparisons multiplied by work done?

Thanks!!