Question

In python

1. Programming Exercise 1

Write a function that will have a list as an input, the task of the function is to check if all the elements in the list are unique,( i.e. no repetition of any value has occurred in the list), then the function returns true otherwise it returns false. Your program should include a main method that call the method to test it.

2. Algorithm Analysis

For the function you implemented in part 1, please calculate T(n), which represents the running time of your algorithm in terms of n. Where n is the length of the list. Then find the order of magnitude of your algorithm (Big O).

3. Algorithms Comparison

Please find another algorithm that solves part 1, write the code, calculate T(n) and find Big O. Then compare the efficiency with the algorithm from part1 to determine the more efficient one.

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.

This is a very big question.
I have solved all of them.
Please give me an upvote dear, Much Appreciated.!!

ALGORITHM TIME COMPLEXITY IS DENOTED IN BOLD LETTERS.

def check_unique(numbers):
    """
    Here we use 2 loops, hence the time complexity is O(N^2)
    :param numbers: a list of numbers.
    :return: Boolean value
    """
    flag = True
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            # Check if there is any repetition
            if numbers[i] == numbers[j]:
                flag = False
                break
    return flag


def check_unique_efficient(numbers):
    """
        Here we use the set conversion, hence the time complexity is O(N)
        :param numbers: a list of numbers.
        :return: Boolean value
    """
    # Convert the numbers to set
    set_nums = set(numbers)
    # Check if the lengths are same
    if len(numbers) == len(set_nums):
        return True
    else:
        return False


# TEST
if __name__ == '__main__':
    numbers1 = [1, 2, 3, 4, 5]
    numbers2 = [1, 2, 3, 1]

    # Call the function1
    print('Is', numbers1, 'Unique? ==> ', check_unique(numbers1))
    print('Is', numbers2, 'Unique? ==> ', check_unique(numbers2))

    # Call the function2
    print('\nIs', numbers1, 'Unique? ==> ', check_unique_efficient(numbers1))
    print('Is', numbers2, 'Unique? ==> ', check_unique_efficient(numbers2))

========

Answer 2

Sure! Let's start by writing the Python function to check if all elements in the list are unique:

pythonCopy codedef are_all_elements_unique(input_list):    # Use a set to check for uniqueness of elements
    unique_set = set(input_list)    
    # If the length of the set is equal to the length of the list, all elements are unique
    return len(unique_set) == len(input_list)def main():
    test_list1 = [1, 2, 3, 4, 5]
    test_list2 = [1, 2, 3, 2, 5]    print(are_all_elements_unique(test_list1))  # Should return True
    print(are_all_elements_unique(test_list2))  # Should return Falseif __name__ == "__main__":
    main()

In this code, we define a function are_all_elements_unique() that takes a list as input. The function converts the list to a set and then checks if the length of the set is equal to the length of the original list. If they are equal, it means all elements are unique, and the function returns True; otherwise, it returns False.

Algorithm Analysis:

The time complexity of the are_all_elements_unique() function is O(n), where n is the length of the input list. The reason is that converting a list to a set takes O(n) time, and comparing the lengths of the set and the list also takes O(n) time in the worst case.

Now, let's find another algorithm to solve the same problem and analyze its time complexity:

pythonCopy codedef are_all_elements_unique_another(input_list):    # Use a dictionary to keep track of element occurrences
    element_count = {}    for element in input_list:        if element in element_count:            return False
        element_count[element] = 1

    return Truedef main():
    test_list1 = [1, 2, 3, 4, 5]
    test_list2 = [1, 2, 3, 2, 5]    print(are_all_elements_unique_another(test_list1))  # Should return True
    print(are_all_elements_unique_another(test_list2))  # Should return Falseif __name__ == "__main__":
    main()

In this alternative algorithm, we use a dictionary to keep track of the occurrences of elements in the input list. We iterate through the list and for each element, we check if it already exists in the dictionary. If it does, it means the element is repeated, and we return False. Otherwise, we add the element to the dictionary. If the loop completes without returning False, it means all elements are unique, and the function returns True.

Algorithm Analysis:

The time complexity of the are_all_elements_unique_another() function is also O(n), where n is the length of the input list. The reason is that iterating through the list and performing dictionary operations takes O(n) time in the worst case.

Both algorithms have the same time complexity of O(n), making them equally efficient in solving the problem of checking if all elements in the list are unique.