Time complexity of an Unique elements list recursion algorithm in python

user_16620040 0
Viewed 42
def is_unique(nums: list[int], first=0, second=0) -> bool:
    if first == len(nums) - 1 and second == len(nums) - 1:
        return True
    else:
        if second == len(nums):
            first += 1
            second = 0
        if first != second and nums[first] == nums[second]:
            return False
        return is_unique(nums, first, second + 1)

How can I analyze the time complexity of my implementation? I think the worst case is O(n^2) of time complexity, and with space complexity the same.

recursion big-o time-complexity list python
1 Answers

First of all, this is a fantastic case study of when not to use recursion in an imperative language. A list of even 40 elements raises a RecursionError on my CPython interpreter and the code is nigh incomprehensible. See Recursion applied to lists vs trees in Python for a deeper look as to why recursion is fundamentally inappropriate for linear (or worse) algorithms.

Linear and cleaner is the Pythonic

def all_unique(it):
    return len(set(it)) == len(it)

As for the analysis, you're right that it's quadratic. But it's good to be able to explain why, because the algorithm might look linear as there's only one recursive call in the code.

The reason it's quadratic is that second = 0 runs O(n) times whenever second == len(nums) - 1 but first != len(nums) - 1 (a base case is when both indices reach the end). This critical line resets all of the progress in the inner "loop" controlled by second + 1 back down to 0 for each increment of the outer "loop" first index, and a huge amount of the progress made iterating through the loop is undone.

It's basically running the classic nested for loop that produces a Cartesian product of pairs of elements in a list:

for first in range(len(nums)):
    for second in range(len(nums)):
        if first != second and nums[first] == nums[second]:
            return False

A tiny optimization that doesn't affect complexity is setting second = first + 1 rather than all the way back down to 0 (and using safer bounds checks, second >= len(nums) - 1).

As for space complexity, you're right if you count the space consumed by call frames. If you don't count call frames, it's O(1).

user_62433520
Related