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 share

Let your friends, followers, and colleagues know about this resource you discovered.

Let's connect

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