similarly, in the top left entry has been replaced with . The remainder of the divide step is to solve for the eigenvalues (and if desired the eigenvectors) of and , that is to find the diagonalizations and . This can be accomplished with recursive calls to the divide-and-conquer algorithm, although practical implementations often switch to the QR algorithm for small enough submatrices. Conquer The conquer part of the algorithm is the unintuitive part. Given the diagonalizations of the submatrices, calculated above, how do we find the diagonalization of the original matrix? First, define , where is the last row of and is the first row of . It is now elementary to show that The remaining task has been reduced to finding the eigenvalues of a diagonal matrix plus a rank-one correction. Before showing how to do this, let us simplify the notation. We are looking for the eigenvalues of the matrix , where is diagonal with distinct entries and is any vector with nonzero entries. The case of a zero entry is simple, since if wi is zero, (,di) is an eigenpair ( is in the standard basis) of since . If is an eigenvalue, we have: where is the corresponding eigenvector. Now Keep in mind that is a nonzero scalar. Neither nor are zero. If were to be zero, would be an eigenvector of by . If that were the case, would contain only one nonzero position since is distinct diagonal and thus the inner product can not be zero after all. Therefore, we have: or written as a scalar equation, This equation is known as the secular equation. The problem has therefore been reduced to finding the roots of the rational function defined by the left-hand side of this equation. All general eigenvalue algorithms must be iterative, and the divide-and-conquer algorithm is no different. Solving the nonlinear secular equation requires an iterative technique, such as the Newton–Raphson method. However, each root can be found in O(1) iterations, each of which requires flops (for an -degree rational function), making the cost of the iterative part of this algorithm . Analysis As is common for divide and conquer algorithms, we will use the master theorem for divide-and-conquer recurrences to analyze the running time. Remember that above we stated we choose . We can write the recurrence relation: In the notation of the Master theorem, and thus . Clearly,