[Problem Reduction] [Algorithms] Problem P is the following: given an array of n

Question

[Problem Reduction] [Algorithms]

Problem P is the following: given an array of n distinct integers, build a binary search tree for these integers.

Problem Q is the following: sort an array of n distinct integers. It is well known that problem Q has a tight lower bound of Omega(n logn).

1 a. Reduce Q to P. In other words, describe an algorithm for solving problem Q by using a solution to problem P

1 b. Use a problem reduction approach to show that P also has a lower bound of Omega(n log n) by using the lower bound of problem Q.

Explanation / Answer

1 a.

Reducing Q to P: An inorder traversal of a BST gives a sorted array. So, Q can be reduced to P in the way that make a BST of the given array and give an inorder traversal of the BST to give the sorted array i.e if we are able to make a BST out of an array, we can sort it.

1 b.

In general, making a BST out of an unsorted array takes Omega(nlogn) time using normal BST procedures.
Using reduction: Since the reduction of Q->P is Omega(n) (reqd for inorder traversal) and as the lower bound of Q is Omega(nlogn), it is evident that lower bound of P should be Omega(nlogn) otherwise, the lower bound of Q would be something else.

For example: Lets say lower bound of P is Omega(x). using the reduction we can say that Lower bound of Q is Omega(x) + Omega(n) which is equal to Omega(n) if x < n or Omega(x) if x>n. As we know that Lower bound of Q is Omega(nlogn), we can conclude that x = nlogn

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.