3
$\begingroup$

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices).

What is the best time lower bound it is known?

Another question is whether the decision version of this eigenvalue problem is known to be in $L$.

$\endgroup$
  • 1
    $\begingroup$ Yes, because of the adversary argument (you need to read the whole input), so it is $\Omega(n)$. I would suggest changing the question so it asks for the best time lower bound that is known. $\endgroup$ – Kaveh Jun 27 '15 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.