Is finding arbitrary length cycles in a graph NP-Hard?
The algorithms mentioned are all fixed-parameter tractable in the size of the cycle.  This means that if you fix the cycle size $k$, there's a polynomial time algorithm for finding the cycle as the number of vertices or edges increases, but the run time still increases exponentially as $k$ increases.  The big-O notation you're looking at only specifies asymptotic run times as the number of edge and vertices increase, but leaves out the possibly large but constant $k!$ factor.