comparing_time_complexity

two_linear_time_algorithms.py

# Uses python3
import sys

def get_majority_element_linear_A(a, left, right):
    elements_dict = {}
    majority_threshold = len(a) // 2
    result = -1  # -1: no majority, 0: majority

    # record all elements into dictionary and test if it's the majority element
    start = time.time()
    for element in a:
        if elements_dict.get(element, -1) >= 0:
            elements_dict[element] += 1
            if elements_dict[element] > majority_threshold:
                result = 0
                break
        else:
            elements_dict[element] = 1
    end = time.time()
    print('A')
    print(end - start)
    
    return result

def get_majority_element_linear_B(a, left, right):
    elements_dict = {}
    majority_threshold = len(a) // 2
    result = -1  # -1: no majority, 0: majority

    # record all elements into dictionary and test if it's the majority element
    start1 = time.time()
    for element in a:
        if elements_dict.get(element, -1) >= 0:
            elements_dict[element] += 1
        else:
            elements_dict[element] = 1
    end1 = time.time()
    print('B-1')
    print(end1 - start1)
    
    start2 = time.time()
    for element_value in elements_dict.values():
        if element_value > majority_threshold:
            result = 0
            break
    end2 = time.time()
    print('B-2')
    print(end2 - start2)
    print((end2 - start2) + (end1 - start1))

    return result


if __name__ == '__main__':    
    import time, random

    n = 20000000
    a = [random.randint(1, n) for _ in range(n)]

    if get_majority_element_linear_A(a, 0, n) != -1:
        print(1)
    else:
        print(0)

    if get_majority_element_linear_B(a, 0, n) != -1:
        print(1)
    else:
        print(0)