Time complexity of computing $AA^T$
If $A$ is an $n \times m$ dense matrix then $AA^T$ is an $n\times n$ matrices given by
$$
(AA^T)_{ij} = \sum_{k=1}^m A_{ik} A_{jk}.
$$
This gives a $\Theta(n^2m)$ algorithm for computing $AA^T$.
If $n \geq m$ then faster algorithms exist, but they are not used in practice (at least in most situations).
If $A$ is sparse, that is, stored as a list of non-zero entries, then $AA^T$ can be calculated using different algorithms which exploit the sparsity of $A$. For example, we can sort the non-zero entries in $A$ according to the second coordinate, and then compute $AA^T$ by going over all $k$ and adding $A_{ik} A_{jk}$ to $(AA^T)_{ij}$ for any $i,j$ in the list of $k$. If $s$ is the sparsity of $A$ and $s_k$ is the number of non-zero entries with second coordinate equal to $k$, then this runs in time
$$
\sum_{k=1}^m \binom{s_k+1}{2} \propto \sum_{k=1}^m s_k^2 \in [s^2/m,s^2].
$$
Therefore the worst-case running time is $\Theta(s^2)$, and the best-case running time is $\Theta(s^2/m)$.