What is the time complexity of my shell sort implementation?
void shellsort(int items[],int n)
{
int j=1;
int d = (pow(3.0,j)-1) / 2;
while(d < ceil(n/3))
{
for(int i=d;i<n;i++)
{
item tmp = items[i];
int k;
for(k = i; k >= d && items[k-d] > tmp; k -= d)
items[k]=items[k-d];
items[k]=tmp;
}
j++;
d = (pow(3.0,j)-1) / 2;
}
}
Knuth proposed his own increment sequence following the formula (3k – 1) / 2 or [1, 4, 14, 40, 121, …].
The time complexity for shell sort using Knuth's increment sequence is O(n^3/2).
Source: https://web.archive.org/web/20181026010135/http://www.stoimen.com:80/blog/2012/02/27/computer-algorithms-shell-sort/
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With