You are given a sequence of at least three integers, which consists of an increasing subsequence followed by a decreasing subsequence. Using the divide and conquer technique, develop a recursive algorithm that finds the index of the turning point in the sequence (that is, the point where it transitions from an increasing subsequence to a decreasing subsequence). For example, in the sequence [7 8 13 22 43 30 16 10), the integer 43 is the turning point and its index is equal to 4 (assuming the starting index is 0). So, the algorithm should return 4. Your implementation should be written in C++.
The function prototype is as follows: int turning Point
(int turning point intA[], int start, int end);
Note that start and end are indices.
Write out a recurrence relation for the time complexity T(n) and then express in Big-Theta notation.