Complexity of computing matrix powers
If the matrix is diagonalizable then taking the $n$th power can be done in time
$$O(D(n)+ n\log n)$$
where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then
$$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.