2

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

}

1 Answer 1

1

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/

1
  • Links get broken and that is why they are not recommended. Try and provide more information next timei.e. a small summary as to how you got to O(n^3/2)
    – Godfrey
    Commented Nov 2, 2019 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.