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 Oct 19 '17 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 Oct 19 '17 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 Oct 19 '17 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 Oct 20 '17 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.

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, privacy policy and cookie policy

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