Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time complexity for Shell sort using Knuth's sequence?

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;
    }

}
like image 882
user1943688 Avatar asked Jul 21 '26 15:07

user1943688


1 Answers

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/

like image 104
roflofogus Avatar answered Jul 24 '26 18:07

roflofogus



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!