Question

Write a python code function that selects top ten max numbers from a sequence of n integers, test it, and determine the Big-Oh of running time for the algorithm (Do not have to prove) -1/i and Write a python recursive function for computing the nth Harmonic number, Hn= test it.

Answer 1

# Solution for 1

The simplest approach would be:

--> Sorting the elements in descending order in O(nLogn)
--> Print the first ten numbers of the sorted array O(k).

CODE:

def max_ten(arr):

    ''' Function code for Ten max elements in an array '''

    # Sort the given array arr in reverse order.

    arr.sort(reverse=True)

    # return the first 10 largest elements

    return arr[:10]

# Testing

arr1 = [1, 23, 12, 9, 30, 2, 50, 2, 56, 89, 10]

arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

arr3 = [90, 80, 70, 60, 50, 40, 30, 20, 10, 5, 4, 3, 2, 1]

print(max_ten(arr1))

print(max_ten(arr2))

print(max_ten(arr3))

assert(max_ten(arr1) == [89, 56, 50, 30, 23, 12, 10, 9, 2, 2])

assert(max_ten(arr2) == [10, 9, 8, 7, 6, 5, 4, 3, 2, 1])

assert(max_ten(arr3) == [90, 80, 70, 60, 50, 40, 30, 20, 10, 5])

# Time complexity: O(nlogn)

# Solution for 2

def harmonic_recursive(n):

    """

    Function that return Nth Harmonic number using recursion

    """

    # H1 = 1

    if n == 1:

        return 1

    else:

        # Hn = H1 + H2 + H3 ... +

        # the result can be rounded using the round function

        return 1.0/n + harmonic_recursive(n-1)

# Testing

print(harmonic_recursive(4))

assert(harmonic_recursive(4) == 2.083333333333333)

assert(harmonic_recursive(20) == 3.597739657143682)

assert(harmonic_recursive(8) == 2.7178571428571425)