В чем разница во временной сложности для этих двух функций powerset?

Question

Здравствуйте, я пытался решить https://leetcode.com/problems/subsets/, который является функцией powerset.

И я написал эти 2 разные версии:

def subsets_hash(s):
    sets = set()
    sets.add(tuple(s))
    for i in range(len(s)):
        tmp_subsets = subsets_hash(s[:i] + s[i+1:])
        for subset in tmp_subsets:
            if subset not in sets:
                sets.add(subset)
    return sets

def subsets_array(s):
    sets = [s]
    for i in range(len(s)):
        tmp_subsets = subsets_array(s[:i] + s[i+1:])
        for subset in tmp_subsets:
            if subset not in sets:
                sets.append(subset)
    return sets

Когда я измеряю время этих двух, используя один и тот же вход, я вижу, что они действительно близки по времени, но если смотреть на код, разве subsets_hash не должен быть быстрее по экспоненциальному коэффициенту?

Второй цикл for for subset in tmp_subsets: выполняется над набором, а не списком, и учитывая, что tmp_subsets увеличивается до размера 2^n (в конечном итоге он содержит все подмножества), тогда я должен быть быстрее с коэффициентом 2^n в первой функции, поскольку установленное владение равно O(1).

Любая помощь в разъяснении этого вопроса приветствуется.