Computational complexity of operations in linear algebra

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Computational complexity of operations
        Linear Algebra
      

To implement computationally efficient machine learning code, you should be using matrix operations. In this section, we highlight the computational complexity of some important matrix operations to help you make faster code.

Note: There are theoretically efficient algorithms available for each of these operations, but it is always safe to assume that the package is not implemented as efficiently as it theoretically could be.

Prerequisites

To understand computational complexity of common matrix and vector operations, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Computational complexity

Operation	Input	Output	Worst case complexity
Dot product of two vectors $(\va, \vb) \rightarrow \va \cdot \vb $	Two $ n$ element vectors	Scalar	$ \BigO{n} $
Matrix multiplication with vector $(\mA, \vx) \rightarrow \mA \vx $	$ (m \times n) $ matrix with $ n$ element vector	$ n$ element vector	$ \BigO{mn} $
Matrix multiplication with matrix $(\mA, \mB) \rightarrow \mA \mB $	$ (m \times n) $ matrix with $ (n \times p) $ matrix	$ (m \times p) $ matrix	$ \BigO{mnp} $
Determinant $ \mA \rightarrow \text{det}(\mA) $	$ (n \times n) $ square matrix	Scalar	$ \BigO{n^{2.3}} $ to $ \BigO{n^4} $
Matrix inversion $ \mA \rightarrow \mA^{-1} $	$ (n \times n) $ square matrix	$ (n \times n) $ square matrix	$ \BigO{n^3} $
Eigendecomposition $ \mA \rightarrow \mQ \mLambda \mQ^T $	$ (n \times n) $ square matrix	Three $ (n \times n) $ square matrices, $ \mQ, \mLambda, \mQ^{-1} $	$ \BigO{n^3} $
Singular value decomposition $ \mA \rightarrow \mU \mD \mV^T $	$ (m \times n) $ matrix	One each of $ (n \times n) $ square matrix, $ (m \times n) $ matrix, and $ (m \times m) $ matrix	$ \BigO{mn^2}, m \le n $

Where to next?

With a sound understanding of computational complexity, you may also choose to explore other advanced topics linear algebra.

Already feeling like an expert in linear algebra? Move on to other advanced topics in mathematics or machine learning.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Let's connect

Please share your comments, questions, encouragement, and feedback.

Operation	Input	Output	Worst case complexity
Dot product of two vectors \((\va, \vb) \rightarrow \va \cdot \vb \)	Two \( n\) element vectors	Scalar	\( \BigO{n} \)
Matrix multiplication with vector \((\mA, \vx) \rightarrow \mA \vx \)	\( (m \times n) \) matrix with \( n\) element vector	\( n\) element vector	\( \BigO{mn} \)
Matrix multiplication with matrix \((\mA, \mB) \rightarrow \mA \mB \)	\( (m \times n) \) matrix with \( (n \times p) \) matrix	\( (m \times p) \) matrix	\( \BigO{mnp} \)
Determinant \( \mA \rightarrow \text{det}(\mA) \)	\( (n \times n) \) square matrix	Scalar	\( \BigO{n^{2.3}} \) to \( \BigO{n^4} \)
Matrix inversion \( \mA \rightarrow \mA^{-1} \)	\( (n \times n) \) square matrix	\( (n \times n) \) square matrix	\( \BigO{n^3} \)
Eigendecomposition \( \mA \rightarrow \mQ \mLambda \mQ^T \)	\( (n \times n) \) square matrix	Three \( (n \times n) \) square matrices, \( \mQ, \mLambda, \mQ^{-1} \)	\( \BigO{n^3} \)
Singular value decomposition \( \mA \rightarrow \mU \mD \mV^T \)	\( (m \times n) \) matrix	One each of \( (n \times n) \) square matrix, \( (m \times n) \) matrix, and \( (m \times m) \) matrix	\( \BigO{mn^2}, m \le n \)