What is the Big O of the algorithem below? Please explain Quicksort Algorithem i

Question

What is the Big O of the algorithem below? Please explain

Quicksort Algorithem

int randomizedPartition(int *a,int p,int r)
{
    int q = p-1, i;
    int temp = 0;
    int randomNum = (rand() % (r-p)) + p;

    temp = a[randomNum];
    a[randomNum] = a[r];
    a[r] = temp;

    for (i = p; i < r; i++)
    {
        if (a[i] <= a[r])
        {
            ++q;
            temp = a[q];
            a[q] = a[i];
            a[i] = temp;
        }
    }

    ++q;
    temp = a[q];
    a[q] = a[r];
    a[r] = temp;

    return q;

}
void randomizedQuickSort(int *a, int p, int r)
{
    if (p < r)
    {
        int q = randomizedPartition(a,p,r);

        randomizedQuickSort(a, p, q - 1);
        randomizedQuickSort(a, q + 1, r);
    }

}

Explanation / Answer

The randomized quicksort is an extension of quicksort where the pivot is chosen randomly. The worst time complexity of Quicksort is O(n^2) but the time complexity of a random quicksort which is above is O(nlogn).In the algorithm, you were choosing the pivot randomly and this has the rendering the worst-case very unlikely, particularly for large arrays.

**Comment for any further queries.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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