Какова сложность (Big -O )этого алгоритма?

Я довольно хорошо знаком с алгоритмическим анализом и могу сказать большое -О о большинстве алгоритмов, с которыми работаю. Но я застрял на несколько часов, не в силах придумать Большой -O для этого кода, который я пишу.

По сути, это метод генерации перестановок для строки. Он работает, делая каждый символ в строке первым символом и комбинируя его с перестановками подстроки меньше этого символа (рекурсивно ).

Если я добавлю код для подсчета количества итераций, я получу что-то между O (N! )и O (N^N ). Но я не мог понять, как анализировать это мысленно. Любое предложение очень ценится!

import java.util.ArrayList;
import java.util.List;

public class Permutation {

   int count = 0;

   List<String> findPermutations(String str) {
      List<String> permutations = new ArrayList<String>();
      if (str.length() <= 1) { 
         count++;
         permutations.add(str);
         return permutations;
      }
      for (int i = 0; i < str.length(); i++) {
         String sub = str.substring(0, i) + str.substring(i + 1);
         for (String permOfSub : findPermutations(sub)) {
            count++;
            permutations.add(str.charAt(i) + permOfSub);
         }
      }
      return permutations;
   }

   public static void main(String[] args) {
      for (String s : new String[] {"a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh"}) {
         Permutation p = new Permutation();
         p.findPermutations(s);
         System.out.printf("Count %d vs N! %d%n", p.count, fact(s.length()));
      }
   }

   private static int fact(int i) {
      return i <= 1 ? i : i * fact(i-1);
   }
}

Редактировать 1:добавить тестовую программу

Редактировать 2:добавить count++в базовом случае