Doubt on quiz of divide&conqr

#1

please explain question no. 7, please show me how to apply master theorm on
T(n)=7*T(n/2)+an^2

#2

T(n) = aT(n/b) + f(n)
here a = 7, b = 2 , f(n) = an^2
n^(logb a) = n^(log2 7) which is greater than f(n) asymptomatically as 2^2 = 4 and 2^3 = 8

So f(n) is type 1 hence T(n) = theta(n^(log2 7))

#3

can u also explain how to find the maximum sum of subarray in an array, using divide and conquer method…

#4

I got the master theorm method.please explain Qno.5 also

#5

The number of comparisons required to find maximum and minimum in the given array of n element using divide and conquer:
a. ciel(3n/2)
b. ciel(3n/2)+2
c. floor(3n/2)
d. floor(3n/2)-2
Answer is d)
Explanation: It will require (3n/2)-2 comparisons

Dry run this code for the number of steps and you will get d

#include
#include
using namespace std;

// Divide & Conquer solution to find minimum and maximum number in an array
void findMinAndMax(int arr[], int low, int high, int& min, int& max)
{
// if array contains only one element

if (low == high)			// common comparison
{
	if (max < arr[low])	 // comparison 1
		max = arr[low];

	if (min > arr[high])	// comparison 2
		min = arr[high];

	return;
}

// if array contains only two elements

if (high - low == 1)			// common comparison
{
	if (arr[low] < arr[high])	// comparison 1
	{
		if (min > arr[low])	 // comparison 2
			min = arr[low];

		if (max < arr[high])	// comparison 3
			max = arr[high];
	}
	else
	{
		if (min > arr[high])	// comparison 2
			min = arr[high];

		if (max < arr[low])	 // comparison 3
			max = arr[low];
	}
	return;
}

// find mid element
int mid = (low + high) / 2;

// recur for left sub-array
findMinAndMax(arr, low, mid, min, max);

// recur for right sub-array
findMinAndMax(arr, mid + 1, high, min, max);

}

int main()
{
int arr[] = { 7, 2, 9, 3, 1, 6, 7, 8, 4 };
int n = sizeof(arr) / sizeof(arr[0]);

// initialize the minimum element by infinity and the
// maximum element by minus infinity
int max = INT_MIN, min = INT_MAX;

findMinAndMax(arr, 0, n - 1, min, max);

cout << "The minimum element in the array is " << min << '\n';
cout << "The maximum element in the array is " << max;

return 0;

}