Am I right to say that the time complexity of this alg is O(n^2 nlogn)? My reasoning is that the nested for loop will have a time complexity of O(n^2) because we iterate through each element in the array provided twice. However I'm a little confused as to how the use of sorted() affects the overall complexity. I currently think that since sorted is not nested in any of the for loops, we simply add its complexity of nlogn to the complexity of n^2. Is this correct?

def kthSmallestPrimeFraction(arr: List[int], k: int) -> List[int]:
    dictionary = defaultdict(list)
    for i in range(len(arr)):
        for j in range(i   1, len(arr)):
            dictionary[arr[i] / arr[j]] = [arr[i], arr[j]]
    sorted_results = sorted(dictionary.keys())
    # return dictionary.get(sorted_results[k-1])
    return dictionary[sorted_results[k - 1]]

CodePudding user response：

Yes, your reasoning is correct.

In big-O notation only fastest growing term is considered, while irrelevant ones are omitted. So this algorithm is O(n^2) - i.e. for really big n (n log n) term is not relevant. https://en.wikipedia.org/wiki/Big_O_notation