Divide-and-conquer eigenvalue algorithm: Difference between revisions

Revision as of 18:38, 19 February 2012

Revision as of 21:21, 7 October 2017

Line 56:

==Analysis==

As is common for divide and conquer algorithms, we will use the [[Master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]] to analyze the running time. Remember that above we stated we choose <math>n \approx m/2</math>. We can write the [[recurrence relation]]:

:<math>T(m) = 2 \times T\left(\frac{m}{2}\right) + \Theta(m^{2})</math>

In the notation of the Master theorem, <math>a = b = 2</math> and thus <math>\log_{b} a = 1</math>. Clearly, <math>\Theta(m^{2}) = \Omega(m^{1})</math>, so we have