Write a C++ function insert_val that inserts a value in a sorted array. The function takes 4 parameters: A an integer array, n the size of the array, count the number of items in the array, and val a data value. The function should return the index of the location that the val is inserted. If the array is already full the value cannot be inserted. In this case the function should return -1. For example, suppose the array A is of size 10 and the contents of the array are {1,3,5,7} (it is sorted and count = 4). If we insert 4 into this array the new contents of the array would be {1,3,4,5,7}, count would be changed to 5 and the function would return 2 (index of 4).

Assume all values in A are distinct. Use the following function header:

int insert_val(int A[], int n, int &count, int val)

// n is the size of the array,

// count is the number of elements in the array

// val is the value to be inserted

// count must be increased by one if insertion is successful

FUNCTION CODE:

What is the running time complexity of your function in Big O notation?

Answer: