Consider the following problem. Given a set S with n3 numbers, the problem is to

Question

Consider the following problem. Given a set S with n3 numbers, the problem is to find two numbers x and y in S such that |x – y| is the second largest.   Give an algorithm of lowest O complexity to solve the problem. State your algorithm in no more than six simple English sentences such as sort the elements, add the numbers etc. (These two operations may not be ones you need in your algorithm.)   Do not write a pseudocode. Circle your complexity among the following.

             (a) O(log(n))            (b) O(n)              (c) O(n log(n))             (d) O(n2)             (e) O(n2 log(n))

Explanation / Answer

This problem almost similar to heap sort. Selecting first max element from the heap. So for first cycle or detecting first max element it takes n iterations. For getting second largest it will reduce some comparisions and it will take log(n) comparisions. So this problem will take complexity as O(n log(n))

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects