Search code examples
pythonalgorithmrecursionbig-ospace-complexity

Big-O Space Complexity of nested operations


If I have nested operations, does this still count as extra-space?

def f(nums1, nums2):
    return len(set(nums1)) < len(set(nums2))

Is function f considered O(1) space complexity as it only creates a boolean value or O(n+m) space complexity as the nested set() operations create two sets of sizes n and m?


Solution

  • O(n+m), Just Like O(n^2 + n) ~ O(n^2)