# Upper bound on the average-case runtime of shell sort

I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $$\Omega(N \log N)$$ in average cases. I want to know the upper bound complexity in average cases, so I write some of code to test it. It seems to be $$O(N\log N)$$ but how to prove it?

Here is the lower bound of average cases analysis:

According to this, for increment sequence $$h_1,\dots,h_p$$, it will have the lower bound of average case

$$\Omega(N\sum_{k=1}^{p}\frac{h_{k-1}}{h_k})$$ where $$h_0 = N$$

Then, the shell sort with the Fibonacci increment sequence will be

$$\Omega(N(\frac{N}{F_n} + \sum_{i=2}^{n}\frac{F_n}{F_{n-1}}) = \Omega(N\log N)$$ where $$F_n$$ is the Fibonacci sequence below $$N$$

• Can you give some references to the claim of $O(\log^2 N)$ in the worst cases and $O(N\log N)$ as lower bound in average cases? It should be mentioned that $O(N\log N)$ (as upper bound) in average cases is an open question. – Apass.Jack Nov 10 '18 at 16:13
• Sorry, I find my proof about the worst case is wrong, so I will delete. The lower bound analysis of average case is derived from this formula. – firejox Nov 12 '18 at 3:03
• Welcome to Computer Science! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. – Raphael Nov 12 '18 at 22:43
• You seem to have a proof attempt there. What's your specific question about it? What are you unsure of? – Raphael Nov 12 '18 at 22:43