1
$\begingroup$

Given this shell sort algorithm implementation:

void shell(float ∗a ,int l ,int r) {
  int i, j, h;
  for ( h = 1 ; 3∗h +1 <= r−l; h = 3∗h + 1 );
  for (; h > 0; h / = 3) {
    for (i = l+h; i <= r; ++ i) {
      for (j = i; j >= l +h && a[j] < a[j−h]; j −= h) {
        swap (a+j−h , a+ j );
      }
    }
  }
}

I want to analyse its time complexity, but I am finding a bit of difficulty to model it mathematically in the form of two summation sigmas, can you help with that please? We know that for Knuth sequence the time complexity is $O(n^{3/2})$

$\endgroup$

0

Your Answer

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