R – Finding the highest 2 numbers- computer science

algorithmcomputer science

I'm trying to figure out an algorithm to find the highest 2 numbers in a list of numbers.

The highest number can be found in n-1 stages, perhaps by doing the fist step of a bubble sort or something along those lines. To me it seems that finding the next highest number as well could be found in a total of 1.5n comparisons on average.

My professor set us homework to write an alogrithm that finds the highest 2 numbers in n + log(n) comparisons. Is this even possible? Any ideas, suggestions?

Edit: When I say n + log(n) I'm not referring to O(n + log n), but rather exactly n + log n

Best Answer

Yes, it's possible to do it in no more than (n + log n). I really can't tell you how without giving away the answer, but let me try. :-)

Take the n numbers, compare them in pairs at a time. Take the ceil(n/2) "winners", and repeat, "like a binary tree". Questions: how many comparisons does it take to find the largest one? How many people does this "winner" win against? To whom might the second largest have lost? So how many comparisons does it now take to find the second largest number?

The answer turns out to be a total of n-1 + ceiling(log n) - 1 comparisons, where the log is to base 2. You can also prove using an adversarial argument that it is not possible to do better than this in the worst case.

Related Solutions

Algorithm to find Largest prime factor of a number

Here's the best algorithm I know of (in Python)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

The above method runs in O(n) in the worst case (when the input is a prime number).

EDIT:
Below is the O(sqrt(n)) version, as suggested in the comment. Here is the code, once more.

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

An NP-complete in computer science

What is NP?

NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(n^k) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.

What is P?

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.

What is NP-Complete?

A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.

In other words:

x is in NP, and
Every problem in NP is reducible to x

So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.

What is NP-Hard?

NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.