Сравнение сложности между двумя реализациями алгоритма «комбинаций»

Question

Рассмотрим следующие две реализации поиска c(n,k), то есть нахождения количества способов выбора n объектов k за один раз. Как соотносятся временные сложности для двух алгоритмов?

Я реализовал реализацию динамического программирования и попробовал несколько тестовых примеров, таких как C (100,25), и это работает довольно быстро. Я пришел к выводу, что сложность по времени для этого решения равна O (n ^ 2).

Другая реализация использует prev_permutation или next_permutation, доступные в библиотеке C ++ STL, взятые из здесь , первоначально из Rosetta Code . Документация к этой функции здесь говорит, что она работает за линейное время до половины расстояния между (первым, последним), так что цикл, который она находится вне, сделает всю сложность снова равной n в квадрате? не уверен насчет этой части, вот где мне нужна помощь).

size_t combinations_dp (int n, int k) {
      vector <vector<size_t>> grid (n + 1, vector<size_t> (k + 1, 0));
      // base cases
      for (int i = 0; i <= n; i ++) {
            for (int j = 0; j <= k; j ++) {
                  if (i == j) grid[i][j] = 1;
                  if (j == 0) grid[i][j] = 1;
            }
      }
      for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                  if (j == 0 || j >= i) continue;
                  else {
                        grid[i][j] = grid[i-1][j-1] + grid[i-1][j];
                  }
            }
      }
      return grid[n][k];
}

void combinations_bits(N, K) {
  vector<bool> arr (K, 1);
  arr.resize(N, 0);
  long long count = 0;

  do {
    count ++;
  } while (prev_permutation(arr.begin(), arr.end()));

  cout << count << "\n";
}

Я не уверен, как сложности двух реализаций сравниваются друг с другом, особенно как функции prev_permutation и next_permutation увеличивают сложность функции по времени.