CODEWITHSUNDEEP
sortingtime-complexityshellsort
user1943688
user1943688

Reputation: 21

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

}

Upvotes: 2

Views: 3140

Answers (1)

roflofogus
roflofogus

Reputation: 11

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/

Upvotes: 1

Related Questions