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.

Improve this question
10
  • 1
    Is this a homework problem? Commented May 9, 2014 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. Commented May 9, 2014 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 Commented May 9, 2014 at 18:40
  • 1
    Sort the array and take the second element. Commented May 9, 2014 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. Commented May 9, 2014 at 18:58

3 Answers 3

Reset to default
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.

Improve this answer
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.

Improve this answer
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".)

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.