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

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Oct 19, 2017 at 10:57
  • $\begingroup$ 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$. $\endgroup$
    – Raphael
    Commented Oct 19, 2017 at 10:58
  • $\begingroup$ 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. $\endgroup$
    – Genxers
    Commented Oct 19, 2017 at 13:01
  • $\begingroup$ 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. $\endgroup$
    – Evil
    Commented Oct 20, 2017 at 0:00

1 Answer 1


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.

To avoid explicit list one may use shrink factor, which behaves similarly to shellsort and use the gap divided by consecutive powers of this factor.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.