0

The problem is to solve it in n+logn−2 (base 2) no of comparisons.

My algorithm is taking some extra space less then (O(n*n)). How can i reduce this extra space without increasing the complexity.

    comparisionarray=[][] (2D array )

    //a function to find the largest.
    findlargest(a,b)
       if(len(a)==1 and  len(b)==1)
          append b to array at ath index in comparisonarray.
          append b to array at bth index comparisionarray.
          return max(a,b)
       else
          return max(findlargest(1stHalfof(a),2ndHalfof(a)),findlargest(1stHalfof(b),2ndHalfof(b))

    input= input_array()
    largest=findlargest(1stHalfof(input),2ndHalfof(input))
    subarray=[array at index largest in comparisionarray]
    2ndlargest=findlargest(1stHalfof(subarray),2ndHalfof(subarray))
    print(2ndlargest)

Edit: It can be done in minimum n+logn−2 comparisons. That is the only condition . This answer on math.stackexchange.com proves it. It has been generalized for nth largest element

Seems that there is a solution at this link stackoverflow. But i am not sure about the extra space and time complexity.

  • 1
    Is this a homework problem? – Blrfl May 9 '14 at 18:24
  • 3
    This problem has some kind-of odd requirements (especially for not being a homework assignment). I can think of an iterative approach that would run in O(n) and use O(n) space, but you aren't clear on the total nature of your constraints, or maybe you haven't described the problem completely. More elaboration would help. – cbojar May 9 '14 at 18:36
  • 2
    there is a solution with O(1) space and O(n) time by keeping the 2 largest values as you iterate for 2*n comparisons – ratchet freak May 9 '14 at 18:40
  • 1
    Sort the array and take the second element. – Daenyth May 9 '14 at 18:44
  • 2
    The problem with the StackOverflow solution is that it hand-waves the "create a binary tree" step. If you're going to do that, you could just as easily sort the array. – Blrfl May 9 '14 at 18:58
6

It looks like you're trying to do some sort of divide-and-conquer that you might find in a sorting algorithm. Sorting and taking the second value from the large end would work, but it's overkill for this problem because you don't really need to have the set of elements sorted when you're done.

The brute-force solution is O(n-1), does at most 2*(n-1) comparisons and occupies space equivalent to two of your set members:

l1 := first_member_in_set  -- Largest value
l2 := first_member_in_set  -- Second-largest value

for each set member m after the first
    if m > l1
        l2 := l1
        l1 := m
    else if m > l2
        l2 := m
    end if
end for

Note that for this to work (and for there to be a second-largest member at all), the set must have at least two members.

3

I think the problem definition could use a bit of work.. Given the assumption that the data isn't sorted I don't see any reason why you can't solve this in effectively 2n comparisons at most, with basically constant memory.. As you read the array you keep two variables. One holds the greatest value you've found so far the other keeps the second greatest. Every time you find a new maximum push the old one down to the second variable.

0

You want a http://en.m.wikipedia.org/wiki/Priority_queue of size 2. This easily generalizes to larger queues.

The usual implementation is an array form of a "heap" http://en.m.wikipedia.org/wiki/Heap_(data_structure) . (This is not a memory allocator kind of "heap".)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.