We study the Krylov state complexity of the Sachdev-Ye-Kitaev (SYK) model for $N \le 28$ Majorana fermions with $q$-body fermion interaction with $q=4,6,8$ for a range of sparse parameter $k$ that controls the number of remaining terms in the original SYK model after sparsification. The critical value of $k$ below which the model ceases to be holographic, denoted $k_c$, has been subject of several recent investigations. Using Krylov complexity as a probe, we find that the peak value of complexity does not change as we increase $k$ beyond $k \ge k_{\text{min}}$ at large temperatures. We argue that this behavior is related to the change in the holographic nature of the Hamiltonian in the sparse SYK-type models such that the model is holographic for all $k \ge k_{\text{min}} \approx k_c$. Our results provide a novel way to determine $k_c$ in SYK-type models.