# Comb sort average complexity

The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, using the standard shrink factor of 1.3 the length of the gaps list is 23. Is this the p mentioned in the wikipedia article? If it is the complexity is omega of 1000^2 / 2^23 ~ 0.120 Someone could please explain what I don't understand? Thank in advance

• If $p$ is fixed, you just get $\Omega(n^2)$. If $p$ is a function of $n$, write it down like that and simplify. If $p$ is anything else, the $\Omega$-expression makes little sense. Commented Oct 19, 2017 at 10:57
• No, you can not insert numbers. Landau notation says something about the limit. "Complexity" is just not defined for any fixed $n$, only for (almost) all $n$. Commented Oct 19, 2017 at 10:58
• Thank you but I asked about p because I didn't understand what it represents. Wekepidia says it is the number of increments. The example was meant to show what I didn't understand. Commented Oct 19, 2017 at 13:01
• It is not the way to use the shrink factor and not the way to use Landau notation, if you want to plug actual numbers it is no longer asymptotic case and it should fail almost always because the constant and lower order factors are missing.
– Evil
Commented Oct 20, 2017 at 0:00

The average-case lower bound for uniformly distributed data is $\Omega(\frac{n^2}{2^p})$, $p$ here denotes the number of increments, not actual gaps.
The number of passes is given as the input with gaps, which are in form of list, say $\{k_1, k_2,\dots,k_p\}$ where given $k$ is single increment value. There are $p$ increments to go, this $p$ is in the equation.