A system of linear differential equations $$ \dot{\mathbf{x}}(t) = \mathbf{A}\mathbf{x}(t)\\ \mathbf{y}(t) = \mathbf{C}\mathbf{x}(t), $$ where $\mathbf{x} \in \mathbb{R}^{n\times 1}$, $\mathbf{y}\in\mathbb{R}^{p\times 1}$, $\mathbf{A}\in\mathbb{R}^{n\times n}$ and $\mathbf{C}\in\mathbb{R}^{p\times n}$, is said to be observable if the vector $\mathbf{x}(t)$ can be inferred from the output $\mathbf{y}(t)$ and its time derivatives for any instant $t$.
Given that $$ \mathbf{x}(t) = e^{t\mathbf{A}}\mathbf{x}(0), $$ it's sufficient to find $\mathbf{x}(0)$ from the output $\mathbf{y}(0)$ and its time derivatives.
The question is, how many derivatives of $\mathbf{y}$ do we need to find a unique solution, if any, for $\mathbf{x}(0)$? Since $\mathbf{x}(0)$ has $n$ components, we need $n$ linearly independent equations to determine it uniquely, so, for the worst case scenario where $p=1$, we'd need $y(0)$ and its first $n-1$ derivatives $$\begin{align*} y(0) &= \mathbf{C}\mathbf{x}(0)\\ \dot{y}(0) &= \mathbf{C}\dot{\mathbf{x}}(0) = \mathbf{C}\mathbf{A}\mathbf{x}(0)\\ \ddot{y}(0) &= \mathbf{C}\ddot{\mathbf{x}}(0) = \mathbf{C}\mathbf{A}^2\mathbf{x}(0)\\ \vdots\\ y^{(n-1)}(0) &= \mathbf{C}\mathbf{x}^{(n-1)}(0) = \mathbf{C}\mathbf{A}^{n-1}\mathbf{x}(0) \end{align*},$$ or, in matrix form $$ \begin{bmatrix} y(0)\\ \dot{y}(0)\\ \ddot{y}(0)\\ \vdots\\ y^{(n-1)}(0) \end{bmatrix} = \underbrace{\begin{bmatrix} \mathbf{C}\\ \mathbf{CA}\\ \mathbf{CA}^2\\ \vdots\\ \mathbf{CA}^{n-1} \end{bmatrix}}_{\mathcal{O}}\mathbf{x}(0). $$ The matrix $\mathcal{O}\in\mathbb{R}^{n\times n}$ is the so-called observability matrix and the system can be determined as observable if and only if the rows of $\mathcal{O}$ are linearly independent of each other. In the general case where $p > 1$, $\mathcal{O}$ will have dimensions $np \times n$ and observability is determined by checking if $\mathcal{O}$ has rank $n$, i.e., full rank.
Given this rather lengthy preamble, here's my question: for the special case where $p= n$, couldn't observability be completely determined by checking if $\mathbf{C}$ has full rank? More generally, if $n = kp$ for some positive integer $k$, wouldn't it be sufficient to check if the slice $$ \mathcal{O}_k = \begin{bmatrix} \mathbf{C}\\ \mathbf{CA}\\ \mathbf{CA}^2\\ \vdots\\ \mathbf{CA}^{k-1} \end{bmatrix} $$ of the matrix $\mathcal{O}$ has full rank? That would save a lot of computation time, manual or otherwise.
Assume $p = n$ for a moment. If $C$ has maximal rank $p = n$ then you can just invert it,
$$x(t) = C^{-1} y(t)$$
and the problem of observability is trivialized since you know the state $x(t)$ exactly. When the rank is deficient, really the argument is no different than when $p < n$, and there is a variation of your claim that is true. Define,
$$\mathcal{O}_k = \begin{pmatrix} C \\ C A^1 \\ \vdots \\ C A^{k-1} \end{pmatrix}.$$
The sequence,
$$\mathrm{rank}\:\mathcal{O}_1, \ldots, \mathrm{rank}\:\mathcal{O}_k, \ldots, \mathrm{rank}\:\mathcal{O}_{n}$$
is a non-decreasing sequence and if any two ranks are equal, the subsequent ranks are as well (the sequence doesn't 'pause'). This can be shown by first noting that if $\mathrm{rank}\:\mathcal{O}_k = \mathrm{rank}\:\mathcal{O}_{k-1}$ then,
$$\mathrm{im}\:\mathcal{O}_k^\top \subseteq \mathrm{im}\:\mathcal{O}_{k-1}^\top.$$
and use this to prove the ranks fail to increase beyond that point. You might have encountered this argument when talking about controllability, the controllability matrix and, in particular, the controllability indices. Since observability is just the dual problem, the argument more or less mirrors that argument. Like in the case of controllability, it is not possible to know a-priori which $\mathcal{O}_k$ to check without computing the sequence at which point why not just compute the final observability matrix.
Of course, you can place an upper bound on the worst case length of the chain. With $p$ independent outputs (i.e. $p = \mathrm{rank}\:C$), the maximal length of the sequence will be $n - p + 1.$ The reason for this bound stems from an argument deriving from the fact that the ranks are non-decreasing and do not pause. If that is what you are looking for, sure, that is the smallest observability matrix you can afford to check.