（先证明上界）
对于上界, 还是计算每一趟排序的运行时间的界, 然后对各趟求和. 这里我们将这些趟($h_t,\ldots,h_2,h_1$)分成两组来考虑.
对于 $h_k > \sqrt{N}$ 的增量, 我们已经知道它们每趟的运行时间上界为 $O(N^2/h_k)$. 虽然这对每个 $h_k$ 都成立的, 但是我们想能否得到更好的上界, 所以对于第二部分的 $h_k$（即 $h_k\leq\sqrt{N}$ 的那些 $h_k$）, 采用不同的估计法.
为什么第二部分可以得到更好的上界? 从直观意义上, （当然增量序列首先要取得好一点.）由于 $h_k$ 之前已经进行过若干趟排序, 因此一些元素的相对大小顺序已经排好. 对于位置 $p$ 上的任意元素 $a[p]$, 当要执行 $h_k$ 排序时, 只有少数元素在位置 $p$ 的左边且大于 $a[p]$.
当对输入数组进行 $h_k$ 排序时, 已经进行了 $h_{k+1}$ 排序和 $h_{k+2}$ 排序.
在 $h_k$ 排序以前, 考虑位置 $p$ 和 $p-i$ 上的两个元素, 其中 $i\leq p$. 如果 $i$ 是 $h_{k+1}$ 或 $h_{k+2}$ 的倍数, 那么显然 $a[p-i]\leq a[p]$. 不仅如此,
Claim: 如果 $i$ 可以表示为 $h_{k+1}$ 和 $h_{k+2}$ 的线性组合（系数是非负整数）, 那么也有 $a[p-i]\leq a[p]$.
Pf. 只要线性表示中系数是非负整数, 则结论是显然的. 首先 $a[p]$ 在某个 $h_{k+1}$ 子列 $S$中, 也在某个 $h_{k+2}$ 子列 $T$ 中. 于是若 $i=sh_{k+1}+th_{k+2}$, 则 $a[p-rh_{k+1}]$ ($r\leq s$) 在子列 $S$ 中, 已经是 $h_{k+1}$ 排序的; 类似的, $a[p-mh_{k+2}]$ ($m\leq t$) 在子列 $T$ 中, 已经是 $h_{k+2}$ 排序的; $a[p-i]\in S\cap T$. 从而 $a[p-i]\leq a[p]$. (Q.E.D of Claim)
例如: 考虑 $h_{k+2}=15$, $h_{k+1}=7$, $h_k=3$. 现在 $i=52=1\times 7+3\times 15$, 令 $p=152$, 从而 $a[100] < a[152]$, 这是因为
\[
a[100]\leq a[107]\leq a[122]\leq a[137]\leq a[152].
\]
现在, $h_{k+2}=2h_{k+1}+1$, 说明 $h_{k+2}$ 与 $h_{k+1}$ 互素. 在这种情况下, 可以证明, 至少和 $(h_{k+1}-1)(h_{k+2}-1)=8h_k^2+4h_k$ 一样大的所有整数都可以表示为 $h_{k+1}$ 和 $h_{k+2}$ 的线性组合.
Pf.
这就告诉我们, 最内层 for 循环体对于这些 $N-jh_k$ ($j=1,2,\ldots$) 位置上的每一个位置最多执行 $8h_k+4=O(h_k)$ 次. 于是我们得到每趟的界为 $O(Nh_k)$.
Claim: Hibbard 增量序列中满足 $h_k < \sqrt{N}$ 的 $h_k$ 大约有一半.
Pf. 注意到最大的 $h_t=2^t-1$ 不妨设为 $[N/2]$. 所以 $N=2^{t+1}-2$. 从而 $\sqrt{N} < \sqrt{2^{t+1}}=2^{(t+1)/2}$. 这说明若 $h_k=2^k-1 < \sqrt{N}$,则有 $k < (t+1)/2$. (Q.E.D. of Claim)
于是我们可以计算总的运行时间了. 不妨设 $t$ 是偶数. 将递增序列分成两部分, 分别计算运行时间估计.
\[
O\biggl(\sum_{k=1}^{t/2}Nh_k+\sum_{k=t/2+1}^{t}N^2/h_k\biggr)=O\biggl(N\sum_{k=1}^{t/2}h_k+N^2\sum_{k=t/2+1}^{t}1/h_k\biggr)
\]
其中
\[
\sum_{k=1}^{t/2}h_k=\sum_{k=1}^{t/2}(2^k-1)=\sum_{k=1}^{t/2}2^k-\frac{t}{2}=\frac{2^{t/2+1}-1}{2-1}-1=2^{t/2+1}-2,
\]
而 $N=2^{t+1}-2$, 所以 $\sum_{k=1}^{t/2}h_k=O(\sqrt{N})$. 类似的,
\[
\sum_{k=t/2+1}^{t}\frac{1}{2^k} < \sum_{k=t/2+1}^{t}\frac{1}{h_k}=\sum_{k=t/2+1}^{t}\frac{1}{2^k-1} < \sum_{k=t/2+1}^{t}\frac{1}{2^{k-1}}
\]
注意到
\[
\frac{1}{2^{t/2}} < \sum_{k=t/2+1}^{t}\frac{1}{2^k} < \sum_{k=t/2+1}^{t}\frac{1}{2^{k-1}} < \frac{2}{2^{t/2}}
\]
因此, $\sum_{k=t/2+1}^{t}\frac{1}{h_k}=O(\frac{1}{\sqrt{N}})$. 故, 运行时间为
\[
O(N\cdot\sqrt{N}+N^2\cdot\frac{1}{\sqrt{N}})=O(N^{3/2}).
\]
（下界的证明）
