Improved lower bounds of the time complexity of shellsort

In this paper we develop the framework of using a parametrized mapping $[\sigma (1),\sigma (2),\cdots ,\sigma (n)]\mapsto \sigma (1)z+\sigma (2)z^2+\cdots \sigma (n)z^n$ to perform runtime analysis on Shellsort. In particular, we show that the worst-case time complexity of Shellsort using Tokuda’s gap sequence proposed in 1992 is at least $\mathrm{\Omega }(N^{1.26})$ with a generalisation of this result to any strictly decreasing gap sequence where each term at most a fixed distance away from a rational geometric sequence, and we also show that strictly decreasing gap sequences giving worst-case Shellsort time complexities of $O(N{\log }^{c}N)$ must have $\mathrm{\Omega }(\log N\mathrm{/}\log \log N)$ terms of order $\mathrm{\Omega }(N\mathrm{/}(\log \log N{)}^c)$.