# Complexity of inverting a diagonal matrix

What is the complexity of inverting a $$n \times n$$ diagonal matrix?

From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its reciprocal.

So is it correct to say that the complexity of inverting a diagonal matrix is $$\mathcal{O}(n)$$?

It's unclear what $$n$$ is in your question. If your matrix has dimensions $$n \times n$$ and your model of computation allows you to perform basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $$O(n)$$ time.
• I forgot to mention the dimension of the matrix, sorry about that. Then is the exact cost of operation is equal to $n$?
• Although it does depend on the representation of your matrix. If it is not represented in a sparse way (a sparse representation could for example simply be an array of the diagonal elements) then the output size is $\Omega(n^2)$ and so you'll need quadratic time, most of it spent writing zeros. Feb 9 at 12:08
• @TR The "exact cost" is as Steven says $O(n)$. Feb 9 at 12:09
• @Tassle Yes, that depends on the representation, but if the operation is essentially the pointwise reciprocal for $O(n)$ elements, I think it is fair to say that you can perform that in $O(n)$ time. You can then return those elements, and the "user" can do with them as they please, e.g. in $O(n)$ time insert them into the matrix. Feb 9 at 12:12
• @PålGD I thought $\mathcal{O}(n)$ is just an estimation of the cost instead of the exact cost? Sorry I'm new to this.