For choosing M elements from array of size N.

Combinations Complexity: Space

• Letters and Combinations in main take N each.
• Index and ChooseThisMany in main take 1 each
• Letters, Start, Size, ChooseThisMany, Combinations, and Store in Choose take 1 each on each invocation. The maximal depth of the recursion, which determines the maximal stack depth for parameters for Choose, is N.
• Total is 2N + 2 + 6N = 8N + 2 which is O(N)

Combinations Complexity: Step Count

• Inserting a step counter

  void Choose(char_array Letters,int Start,int Size,int ChooseThisMany,
  char_array Combination,int Store) {
  
  int Index;
  
  GlobalCounter++; //----For condition
  if (ChooseThisMany == 0) {
      for (Index = 0; Index < Store; Index++) {
          GlobalCounter++; //----For each iteration
          cout << Combination[Index];
          GlobalCounter++; //----For cout
          }
      GlobalCounter++; //----For last iteration
      cout << endl;
      GlobalCounter++; //----For cout
      }
  else {
      GlobalCounter++; //----For condition
      if (ChooseThisMany <= (Size - Start)) {
          Combination[Store] = Letters[Start];
          GlobalCounter++; //----For assignment
          Choose(Letters,Start+1,Size,ChooseThisMany-1,Combination,Store+1);
          GlobalCounter++; //----For condition
          if (ChooseThisMany < (Size - Start)) {
              Choose(Letters,Start+1,Size,ChooseThisMany,Combination,Store);
              }
          }
      }
  }

• Some step counts

  Step count for 3 1 is 27
  Step count for 3 2 is 41
  Step count for 3 3 is 21
  Step count for 4 1 is 36
  Step count for 4 2 is 78
  Step count for 4 3 is 72
  Step count for 4 4 is 27
  Step count for 5 1 is 45
  Step count for 5 2 is 126
  Step count for 5 3 is 166
  Step count for 5 4 is 111
  Step count for 5 5 is 33