Понимание разницы во временной сложности двух способов создания подмножеств

Недавно я проводил анализ сложности двух отдельных методов генерации подмножеств данного набора. Для этого вопроса я удаляю все несущественные компоненты кода, а это означает, что обе эти функции являются не более чем «фиктивными» примерами, не имеющими реальной цели. Предположим, что lst представляет список размером n, а curr представляет текущее подмножество и что каждый метод изначально будет вызываться с i, установленным в 0.

Метод 1:

def meth_1(i):
   if i == len(lst):
      return
   
   curr.append(lst[i])
   meth_1(i + 1)
   curr.pop()
   
   meth_1(i + 1)

Метод 2:

def meth_2(i):
   if i == len(lst):
      return
   
   for j in range(i, len(lst)):
      curr.append(lst[j])
      meth_2(j + 1)
      curr.pop()

Хотя обе эти реализации, похоже, дают один и тот же результат, мне сложно тщательно проанализировать их временную сложность в наихудшем случае. В качестве общего подхода к анализу временной сложности рекурсии я суммирую общее количество работы на всех уровнях дерева рекурсии; Я знаю, что в более сложных примерах каждый рекурсивный вызов может выполнять разный объем работы, хотя есть простые способы обойти это.

Применять этот подход к meth_1 — обычное дело. Построение древовидной диаграммы, пожалуй, самый интуитивный способ сделать это:

На диаграмме выше есть три столбца для каждого уровня дерева рекурсии. Узлы представляют общее количество узлов на уровне, уровень представляет уровень дерева (с нулевым индексом), а общая работа представляет собой общую работу, выполненную на этом уровне. Здесь мы предполагаем, что нерекурсивная работа данного вызова является константой c. Мы знаем, что наше рекурсивное дерево будет иметь n + 1 всего уровней, поскольку каждый уровень будет увеличивать i на 1, пока не будет достигнуто значение n. Также стоит отметить, что общий объем работ, выполненных на каждом уровне, можно смоделировать как $\sum_{i=0}^{n+1} 2^ic = \frac{c(1-2^{n+1}) }{-1} = O(2^n)$.

Однако мне трудно проанализировать временную сложность meth_2. В этом случае нарисовать рекурсивную диаграмму гораздо сложнее по нескольким причинам. Во-первых, каждый вызов функции будет выполнять переменное количество вызовов рекурсии, в отличие от meth_1, где каждый вызов выполняет два последовательных рекурсивных вызова. Аналогично, каждый из рекурсивных вызовов meth_2 будет находиться на другом «уровне»; это контрастирует с meth_1, где каждый последующий рекурсивный вызов на уровне i находился на уровне i + 1. Я пишу все это, чтобы спросить: как мне проанализировать временную сложность meth_2?