-1
$\begingroup$

I am trying to prove that the following statements are true:

* The average time complexity of the quick sort is O(n log2 n). 

* The average time complexity of the randomized quick sort is Θ(n log2 n). 

* The worst case time complexity of the quick sort is Θ(n^2). 

* The worst case time complexity of the randomized quick sort is O(n^2). 

I wrote a program for quicksort and randomized quick sort

#quicksort

def partition(arr,low,high):
    pindex = low         
    pivot = arr[high]     
    print(arr)
 
    for j in range(low , high):
 
        if   arr[j] <= pivot:
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print(arr)
 
    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)
 

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        print(arr)


arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)#quicksort

def partition(arr,low,high):
    pindex = low         
    pivot = arr[high]     
    print(arr)
 
    for j in range(low , high):
 
        if   arr[j] <= pivot:
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print(arr)
 
    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)
 

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        print("pi",pi)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        print(arr)


arr = [1, 4, 2, 7, 8, 3]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)

and

#randomized quicksort

import random
def partition(arr,low,high):
    print(arr)
    pindex = low         
    pivot_index = random.randint(low,high-1)
    pivot=arr[pivot_index]
    n_comparisons = 0  
    arr[high],arr[pivot_index]=arr[pivot_index],arr[high]
    print("pivot:", arr[pivot_index])
    for j in range(low , high):
 
        if   arr[j] <= pivot:
            n_comparisons += 1 
            arr[pindex],arr[j] = arr[j],arr[pindex]
            pindex = pindex + 1
            print("n_comparisions:", n_comparisons)
 
    arr[pindex],arr[high] = arr[high],arr[pindex]
    return (pindex)
 

def quickSort(arr,low,high):
    print(arr)
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
 

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
print(arr)
[10, 7, 8, 9, 1, 5]
[1, 7, 8, 9, 10, 5]
[1, 5, 8, 9, 10, 7]
[1, 5, 7, 9, 10, 8]
[1, 5, 7, 8, 10, 9]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
Sorted array is:
[1, 5, 7, 8, 9, 10]
[1, 4, 2, 7, 8, 3]
[1, 4, 2, 7, 8, 3]
[1, 2, 4, 7, 8, 3]
pi 2
[1, 2, 3, 7, 8, 4]
[1, 2, 3, 7, 8, 4]
pi 1
[1, 2, 3, 7, 8, 4]
[1, 2, 3, 7, 8, 4]
pi 3
[1, 2, 3, 4, 8, 7]
pi 4
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 7, 8]
[1, 2, 3, 4, 7, 8]
Sorted array is:
[1, 2, 3, 4, 7, 8] 

As I worked through quick sort I was able to create the following output.

I'd like to use the results from this to show that the statements above are true. I would appreciate it if someone could help me with this. There is never enough time, thank you for yours.

$\endgroup$
1
  • $\begingroup$ Please ask only one question per post. I see four different things you are trying to prove, which is about four different questions. It is not clear what your code has to do with the question. We discourage questions that are the statement of an exercise-style task and a request for us to do it. See here for tips on asking questions about exercise-style problems. $\endgroup$
    – D.W.
    Feb 12, 2023 at 4:43

1 Answer 1

2
$\begingroup$

There are many pitfalls in your approach.

In the first place, you cannot obtain any reliable information on the time complexity of a program by timing it. Because for a small number of elements, the time is heavily polluted by many ancillary "setup" processes and many non-deterministic perturbations, and for a large number of elements, the memory accesses do not take constant time. Fortunately, the case of small numbers (like your example) is irrelevant as for asymptotic analysis it is meaningless.

It is better to instrument the code and count the comparisons and the data moves.

Even if you had reliable timing data, fitting a function to empirical data is extremely hazardous (for instance, you could probably not tell $n\log n$ from $n\sqrt n$). And to truly validate it, you should go to astronomical values of $n$, such that neither your computer nor your patience can afford.

To measure an average time complexity, in principle you need to perform several runs on different data sets and average the results. This is doable (with the above reservations); as a byproduct, you can get an estimate of the dispersion. Notice anyway that there isn't a single "average time": this time depends on the chosen statistical distribution of the input permutations.

There is no difference between running the algorithm on random data, and running the randomized algorithm on any data, so you can spare one of the first two tests.

The worst-case times are virtually inaccessible with random data, as they occur with astronomically small probabilities, plus you have no way to known that you reached the worst case. A reliable method is to try all permutations, but even for moderate sizes (say $n\ge15$) this is impractical.

To summarize, you don't analyze an algorithm by experimentation, but by reasoning.

$\endgroup$

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.