Work out the O() running time for the following recursive function. Show all your working.

Question

void sort(int vals[], int n)

{

if (n == 1)

return;

sort(vals, n-1); // sort first n-1 values

// now insert vals[n-1] into correct position in vals[]

int temp = vals[n-1];

int i = n-1;

while ((i > 0) && (vals[i-1] > temp)) {

vals[i] = vals[i-1]; i--;

}

vals[i] = temp;

}

Answer 1

Summary: this is a recursive implementation of insertion sort, which runs in O(n²) in its average and worst cases.

Explanation:

void sort(int vals[], int n) {

if (n == 1)

return;

// This line will be recursively called n - 1 times. Add the current call and

// you'll run sort() n times.

sort(vals, n - 1);

int temp = vals[n - 1];

int i = n - 1;

// This loop could potentially go through all elements in the current

// recursive call.

//

// The average number of elements per recursive call is:

// avg([1, 2, 3, ..., n-1, n]) = n / 2

while ((i > 0) && (vals[i - 1] > temp)) {

vals[i] = vals[i - 1];

i--;

}

vals[i] = temp;

}

Given that you have n calls to sort() and each call to sort() iterates through, on average, n / 2 elements, your Big-O time is thus:

O(n * (n / 2)) → O(n²)