Divide and Conquer

In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of

• Sorting/Divide

• Conquer/Solve

• Merge/Combine

• Divide/Break

Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array, partition returns the pivot element

• public static void quickSort(int[] arr, int low, int high)

  {

  int pivot;

  if(high>low)

  {

  pivot = partition(arr, low, high);

  quickSort(arr, low, pivot-1);

  quickSort(arr, pivot+1, high);

  }

  }

• public static void quickSort(int[] arr, int low, int high)

  {

  int pivot;

  if(high<low)

  {

  pivot = partition(arr, low, high);

  quickSort(arr, low, pivot-1);

  quickSort(arr, pivot+1, high);

  }

  }

• public static void quickSort(int[] arr, int low, int high)

  {

  int pivot;

  if(high>low)

  {

  pivot = partition(arr, low, high);

  quickSort(arr, low, pivot);

  quickSort(arr, pivot, high);

  }

  }

What is the worst case complexity of QuickSort?

• O(nlogn)

• O(logn)

• O(n)

• O(n^2)

Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is first element?

• 6 4 3 7 11 9 14 12

• 6 3 4 7 9 14 11 12

• 7 6 14 11 9 4 3 12

• 7 6 4 3 9 14 11 12

The best case behaviour occurs for quick sort is, if partition splits the array of size n into __________

• n/2 : n/3

• n/4 : 3n/4

• n/2 : (n/2) – 1

• n/4 : 3n/2

A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed to sort 200 elements will be approximately

• 60.2 sec

• 20 sec

• 45.54 sec

• 31.11 sec

The running time of merge sort can be reccursively represented by

• T(n)=2T(n/2)+n

• T(n)=2T(n/4)+n

• T(n)=4T(n/2)+n

• T(n)=3T(n/2)+n

If the recurrence relation for a binary search is represented by T(n)=aT(n/b)+O(n^d) then the value of a+b+d is

• 0

• 1

• 3

• 4

Which of the following is true

• Merge sort takes T(n)=2T(n/2)+O(n)

• Merge sort takes T(n)=3T(n/2)+O(n)

• Quick sort takes O(n^2) time in its average case

• None of the above

The step(s) in the divide and conquer process that takes a recursive approach is said to be

• Conquer/Solve

• Merge/Combine

• Divide/Break

• All of the mentioned