Running time of recursive function using datetime library in python

Question

I have 2 functions in python to sort a list using quicksort

import datetime
def partition(arr, low, high):
    i = (low - 1)  # index of smaller element
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

def quickSort(arr, low, high):
    dt_started = datetime.datetime.utcnow()

    if low < high:
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr, low, high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    dt_ended = datetime.datetime.utcnow()

    total_time = (dt_ended - dt_started).total_seconds()

    return total_time

Where dt_started is the start time for the function and dt_ended is the end time. From my main, i am calling the function like this:

total_time=quickSort(arr,0,n-1)

where arr is the list I want to sort and n is its size.

My question is, will the quickSort() function return the correct running time as there will also be multiple recursive calls in the function.

Answer 1

Yes, it will. The variables are local to the function (at each call), so even if you call recursively the function, they are not overwritten.

You can test it with putting some trace in the code. For example, you can print the values of dt_started and dt_ended in your code (I'm not going into what the code itself does):

def quickSort(arr, low, high):
    print '>> called quickSort'
    print '  low:', low
    print ' high:', high
    dt_started = datetime.datetime.utcnow()
    print 'dt_started:', dt_started
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    print '> other calls finished'
    print '  low:', low
    print ' high:', high
    print 'dt_started:', dt_started        
    dt_ended = datetime.datetime.utcnow()
    print '  dt_ended:', dt_ended
    total_time = (dt_ended - dt_started).total_seconds()
    return total_time

Running this function with a small array:

In [4]: a = range(1,100)

In [5]: quickSort(a,0,1)
>> called quickSort
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
>> called quickSort
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
> other calls finished
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
  dt_ended: 2019-03-26 14:59:41.841138
>> called quickSort
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
> other calls finished
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
  dt_ended: 2019-03-26 14:59:41.841327
> other calls finished
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
  dt_ended: 2019-03-26 14:59:41.841370
Out[5]: 0.000495

As you can see, the dt_started at the end of the calls is the same as the first one. It retains the value it had at the first call and the total computed time will be correct.