The complexity of checking for short cycles in a graph

In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199).

Next, as for determining the existence of long cycles, I don't hold much hope for efficient algorithms. However, what about short cycles? For instance, 3-cycles, 4-cycles, and so on. For a $k$-cycle, at what value of $k$ does the algorithmic complexity transition from polynomial time to non-polynomial time? Is there a clear boundary?

If your graph has $n$ vertices and you’re interested in $k$-cycles, then a brute-force inspection will look at each of the $n \choose k$ possible $k$-tuples. Thus, assuming that $k$ is small—in other words, that $k = O(1)$—that approach is $\Theta(n^k)$.

StackExchange Computer Science Q#161786, answer score: 5