CODEWITHSUNDEEP
algorithmrecursionbig-otime-complexity
Umar Tahir
Umar Tahir

Reputation: 1

Algorithm implementation using divide and conquer paradigm

I am required to implement a recursive version for this algorithm. Being fairly new to recursion, I have a very vague idea of how to approach this problem.

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference.

Upvotes: 0

Views: 58

Answers (1)

templatetypedef
templatetypedef

Reputation: 373112

One observation that might make your life a lot easier here is to recognize that if the numbers are sorted order, then the pair of numbers with the smallest difference must be adjacent to one another. Therefore, a simple algorithm would be to sort the elements, then look at all adjacent pairs to find the smallest.

Since you're asked to do this recursively, you might try to solve each part recursively. For the first part - sorting - there are a ton of good recursive sorting algorithms - mergesort and quicksort to name two of them. Mergesort runs in time O(n log n), so that's a good starting point.

As for how to find the best pair using recursion, here's some insights that might let you get a recursive solution:

  • If there are only two elements in the array, they have to have the smallest difference because there aren't any other options.
  • If there are three or more elements in the array, then either the best pair uses the first element or it doesn't. If it does use the first pair, the value is given by the first two elements. If it doesn't, then you can (recursively) compute the best pair of elements by looking for the pair with the minimum difference in the subarray excluding the first element.

This overall approach runs in time O(n log n). I'll leave the details as an exercise, since this seems like it's a problem set question.

Upvotes: 2

Related Questions