Mergesort sorts a list by dividing it in half, recursively sorting the halves, and then merging the halves back together, exploiting the fact that it is easy to combine sorted lists into a sorted list, and that if you divide a list often enough the parts become sorted automatically (becoming singleton). Given any algorithm of this sort, in which the data is divided in half and then combined in linear time, we have T(n)=<2T(n/2)+cn, and T(2)=<c. The sum of this function as it is recursively applied can be found by looking at each level of recursion; the first takes cn time, the second 2c(n/2)=cn, and so forth; there are log_2 n layers, giving a running time of O(n log_2 n). One can also solve the equation directly by substituting c(n/2)(log_2 n/2) for T(n/2); this gives T(n)=<2c(n/2)(log_2 n/2)+cn=cn[(log_2 n)-1]+cn=cn(log_2 n), giving O(n log n); given an asymptotic running time, one can plug it in with generic constants and simplify to find the constant (here c) that would create the desired cancellation.

No insights.

No questions.

No complaints.

Recursive algorithms can be classified by the form of their recurrence relation, the divisions they make and complexity of the combination. A generalization of the quicksort recurrence is T(n) ⇐ qT(n/2)+cn; total work in level j is (q/2)^jcn, and the implied summation simplifies to O(n^(log_2q)-1). One can identify such relations, where what to plug in is not obvious, by plugging in an expression with extra degrees of freedom, and then identifying values that complete the substitution. A different extension is given by T(n) ⇐ 2T(n/2)+cn^2; this gives O(n^2).

No insights.

No questions.

No complaints.