What is the big-O of the shellsort() function provided in Figure? Briefly explai

Question

What is the big-O of the shellsort() function provided in Figure? Briefly explain how you arrived at your answer. Remember big-O measures the worst case runtime scenario.

/**

*Shellsort, using Shell’s (poor) increments.

*/

template <typename Comparable>

void shellsort ( vector<Comparable> & a)

{

for ( int gap = a.size() / 2; gap > 0; gap /= 2)

                        for ( int i = gap; i < a.size(); ++i )

                        {

                                    Comparable tmp = std::move( a[ i] );

                                    int j = i;

                                    for ( ; j >= gap && tmp < a[ j – gap ]; j-= gap )

                                                a [ j ] = std:: move ( a [j – gap] );

                                    a [ j ] = std:: move (tmp);

                        }

}

Explanation / Answer

Shell Sort Time Complexity is For      Best Case we can say    O(n).

                                                       Average Case is O((n log (n))^2).                                   

Shell sort does less than O(n ^3/2) Comparisons for this increment sequence.

Worst case of Shell Sort in Time Complexity O((n log(n))^2).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.