Какова среда выполнения этого рекурсивного кода?

Question

Мне интересно, какой будет среда выполнения следующей рекурсивной функции:

  int f(int n) {
    if (n <= 1) {
      return 1;
    }
    return f(n-1) + f(n-1);
  }

Если вы думаете об этом как о дереве вызовов, каждый узел будет иметь 2 ветви. Количество узлов в этом дереве вызовов будет равно 2⁰ + 2¹ + 2² + 2³ + ... + 2 ^ n, что эквивалентно 2 ^ (n + 1) - 1. Таким образом, временная сложность этой функции должна быть O ( 2 ^ (n + 1) -1) при условии, что каждый вызов имеет постоянное время O (1) - я прав? Согласно книге, откуда у меня этот пример, сложность времени составляет O (2 ^ n). Я в замешательстве - что мне не хватает?

Answer 1

Система обозначений Big-O игнорирует постоянные множители и члены более низкого порядка. Таким образом, O (2 ^ (n + 1) -1) эквивалентно O (2 ^ n).

O(2^(n+1)-1) = O(2^n * 2^1 - 1)

Мы отбрасываем постоянный множитель 2 ^ 1, а затем отбрасываем член младшего порядка -1, когда 2 ^ n растет асимптотически быстрее.