Временная сложность рекурсии внутри цикла for с переменной итерацией? ⇐ JAVA

[Anonymous]

Я решал задачу LeetCode, которую я решил с помощью двух кодов с разной временной сложностью, но оба давали одинаковое время выполнения.
вызов кода

Код: Выделить всё

class Solution {
Integer max = Integer.MIN_VALUE;

int solve(int[] freq) {
dfs(freq, 0, 0)
}
return max;
}

массив freq содержит установленный бит для строчных букв английского алфавита,
например, ['abc', 'de'] -> [ 7, 24]
где 7(

Код: Выделить всё

111

), представляющий частоту как {c: 1, b: 1, a: 1
и 24(

Код: Выделить всё

11000

), представляющий частоту как {e: 1, d: 1, c: 0, b: 0, a: 0
Первый код:

Код: Выделить всё

void dfs(int[] freq, int idx, int value) {
max = Math.max(max, value);

if (idx >= freq.length) return;

dfs(freq, idx + 1, value | freq[idx]);
dfs(freq, idx + 1, value);
}

Я знаю, что временная сложность приведенного выше кода будет O(2^n), потому что для каждой рекурсии создаются еще две рекурсии.
И второй код:

Код: Выделить всё

void dfs(int[] freq, int idx, int value) {
max = Math.max(max, value);

for (int i = idx; i < freq.length; i++) {
dfs(freq, i + 1, value | freq[i]);
}
}

Я не понимаю, как вычислить временную сложность второго кода. Поскольку цикл начинается с переменной idx, а idx увеличивается (из-за i + 1) при каждом рекурсивном вызове, что уменьшает итерацию цикла.
Правильно ли сказать, что второй код имеет временную сложность: O(n^m), где n — максимальная высота рекурсивного дерева, а m — сложность цикла?
Кроме того, когда я отправляю оба кода, они имеют одинаковую среду выполнения. Это также из-за переменной idx в цикле for второго кода, благодаря которой он становится эквивалентным первому коду?

Подробнее здесь: https://stackoverflow.com/questions/784 ... -iteration