I have an algorithm that receives a labeled graph on n vertices and a number k as input and proceeds by checking whether the cycles of length less than k are contained in the graph. A cycle in this context is a closed path where each vertex is only allowed to appear once.

For a given k, I'm interested in how often I can expect to not find all cycles there are so that I'm able to get a better feeling for the cost-value ratio of k - the computations get more and more costly with rising k (which is no surprise, given that finding a hamilton cycle is NP-hard).

Checking each cycle is not an option - the algorithm is supposed to be used with k strict less than n and I want to know whether its worth it to increase k by a certain amount. So I'd like to know how big the propability is that an input graph contains a cycle of length at least k - given that every graph on n vertices is equally likely to be the input.

Equally, I'm interested in the number of labelled graphs on n vertices that contain a cycle of length at least k. Are there any explicit formulas or results in general for this?