1
$\begingroup$

I would like to estimate the number of comparisons in ShellSort. I'm using $h_s = 2^s-1$, where $s=\left \lfloor{\log(n)}\right \rfloor, \left \lfloor{\log(n)}\right \rfloor -1, \dots, 1 $ ;

I know that it is good idea to part it into two cases: (1) $s=\left\lfloor{\log(n)}\right \rfloor \left \lfloor{\log(n)}\right \rfloor -1, ..., \left\lfloor{\log(\frac{n}{2})}\right \rfloor$

(2) $\left\lceil{\log(\frac{n}{2})}\right \rceil, \left\lceil{\log(\frac{n}{2})}\right \rceil -1, ..., 1 $

Could somebody give me a clue ? I am not asking to solution, but only help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.