Where does this array-based fast-growing function fall in the fast-growing hierarchy, and how does it compare to TREE(n)?

Question

[See below for a clarification edit and progress thus far]

So I have been reading into the "fast-growing hierarchy" of functions, and I devised this (somewhat convoluted) function for generating very large numbers, based on an array (there may be similarities with Bower's Array Notation, but I don't think it is identical).:

(source code in C for this function is given below)

1. $\quad S_{\{0\}} (n) = n \uparrow^{\ n-2} n; \text{ where } S_{\{0\}}(0) = 1, S_{\{0\}}(1) = 2, \text{ and } S_{\{0\}}(2) = 4 \text{.}$
2. $\quad S_{\{k\}} (n) = S_{\{k-1\}}^{n} (n), \text{ where } S_{\{k-1\}} \text{ is nested $n$ times.}$
3. $\quad S_{\{ k_1, k_2, \ldots, k_n, 0\}} (n) = S_{\{ k_1, k_2, \ldots, k_n\}} (n) \text{.}$
4. $\quad S_{\{ k_1, k_2, \ldots, k_{n-1}, k_n\}}(n) = S_{\{ k_1, k_2, \ldots, S_{\{ k_1, k_2, \ldots, k_{n-1}, k_n - 1\}}(n), k_n - 1\}}(n) \text{.}$
5. $\quad _{k}S(n) = S_{\{n, n, \ldots, n, n\}} (n), \text{where there are $k$ instances of $n$ in the array.}$
6. $\quad M(n)=\text{ }_{n}S(n) \text{.}$

As an example, $S_{\{n, 1\}} (4) = S_{\{S_{\{n,0\}}(4),0\}} = S_{\{S_{\{n\}}\}}(4)$

This function $M(n)$ grows quite rapidly, with $M(0) = 1$, $M(1) = 2$, and $M(2) >>$ Graham's Number.

It seems to me that $S_{\{0\}}(n)$ would be analogous to $f_{\omega}$ in the fast-growing hierarchy, and $_{1}S(n)$ would be similar to $f_{\omega 2}$. I think that $_{2}S(n)$ would be similar to $f_{\omega^2}$, and $_{3}S(n)$ to $f_{\omega^{\omega}}$, but I am unsure about $M(n)$ in general.

Is there any way to determine where exactly $M(n)$ lies in the fast-growing hierarchy, or at least an upper and lower bound for it? Also, how does $M(3)$ or $M(M(3))$ compare to $TREE(3)$, where $TREE$ refers to Friedman's TREE sequence (http://googology.wikia.com/wiki/TREE_sequence)?

If it helps, I have created a C-language program which implements this function:

/* An implementation of the fast-growing "M" function */

#include <stdio.h>

/*
An implementation of the hyperoperation sequence (analogous to S0(n)).
*/
int hyp(int n, int a, int b) {
    if(n == 0) {return b+1;}
    else if(n == 1 && b == 0) {return a;}
    else if(n == 2 && b == 0) {return 0;}
    else if(n >= 3 && b == 0) {return 1;}
    else {return hyp(n-1,a,hyp(n,a,b-1));}
}

/* 
An implementation of the "S" function, with an array input
*/
int S(int inputArr[], int n) {
    int size = sizeof(inputArr)/sizeof(inputArr[0]);
    if(size == 1) {
        if(inputArr[0] == 0) {return hyp(n,n,n);}
        else {
            int counter = 1;
            int passArray[]={inputArr[0]-1};
            int k = S(passArray,n);
            while(counter < n) {
                k = S(passArray,k);
                counter = counter+1;
            }
            return k;
        }
    }
    else if(inputArr[size-1] == 0) {
        int newArray[size-1];
        int f;
        for(f = 0; f < size-1; f++) {
            newArray[f] = inputArr[f];
        }
        return S(newArray,n);
    }
    else {
        int newArray[size];
        int midArray[size];
        int f;
        for(f = 0; f < size-2; f++) {
            newArray[f] = inputArr[f];
        }
        for(f = 0; f < size-1; f++) {
            midArray[f] = inputArr[f];
        }
        midArray[size-1] = inputArr[size-1]-1;
        newArray[size-1] = inputArr[size-1]-1;
        newArray[size-2] = S(midArray,n);
        return S(newArray,n);
    }
}

/*
The "M" function, based on the "S" function defined above
*/
int M(int n) {
    int callArray[n];
    int k;
    for(k = 0; k < n; k++) {callArray[k] = n;}
    return S(callArray,n);
}

int main() {
    int n = 0;
    int k = M(n);
    printf("M(%d) = %d\n",n,k);
    n = 1;
    k = M(n);
    printf("M(%d) = ",n);
    printf("%d\n",k);
    n = 2;
    printf("M(%d) = ",n);
    k = M(n);
    printf("%d\n",k);
return 0; }

---

EDIT: Clarification and Progress

---

I think my original definition for the function may have been difficult to follow and I could very well have made a mistake in specifying it. Here is an example of how I intended it to work, as a clarification: $$S_{3,3,2} (n) = S_{3,S_{3,3,1} (n),1} (n) = S_{3,S_{3,S_{3,0} (n),0} (n),1} (n) = S_{3,S_{3,S_3 (n)} (n), 1} (n) = S_{3, S_{3, S_{3, S_3 (n)} (n)} (n)} (n).$$ As one can see, each term creates a huge number of nestings of the S function in its previous terms, and once the final term reaches zero, the process continues for the previous term (which is now likely a nesting of many S functions, as seen in the example), continuing on until there is only one term left, which would likely be quite large.

Answer 1

First look

$$S_{\{0\}}(n)\approx f_\omega(n) \\ \Rightarrow S_{\{k\}}(n)\approx f_{\omega+k}(n)$$

Property: $S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n)=g^{k_m+1}(k_{m-1}) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)$

$$S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n) \\=S_{\{k_1,k_2,…,X_1,k_m-1\}}(n) \text{ with } X_0=k_{m-1} \text{ and } X_{i+1}=S_{\{k_1,k_2,…,X_i,k_m-1\}}(n) \\=S_{\{k_1,k_2,…,X_2,k_m-2\}}(n) \\=\cdots \\=S_{\{k_1,k_2,…,X_{k_m-1},1\}}(n)\\=S_{\{k_1,k_2,…,X_{k_m}(n)\}}(n) \\=X_{k_m+1} \\=g^{k_m+1}(k_{m-1}) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)$$

Proof by induction $S_{\{k_1,k_2,…,k_{m-1},k_m\}}(n)\approx f_{\omega\cdot2+m-1}(k_m+1)$

Base case: $m=2$

$$S_{\{k_1,k_2\}}(n)=g^{k_2+1}(k_1) \text{ with } g(x)=S_{\{x\}}(n)\approx f_{\omega+x}(n)\approx f_{\omega\cdot2}(x) \\ S_{\{k_1,k_2\}}(n)\approx f^{k_2+1}_{\omega\cdot2}(k_1)\approx f_{\omega\cdot2+1}(k_2+1)$$

Succesor case: $m+1$

$$S_{\{k_1,k_2,…,k_{m},k_{m+1}\}}(n)=g^{k_{m+1}+1}(k_m) \text{ with } g(x)=S_{\{k_1,k_2,…,x\}}(n)\approx f_{\omega\cdot 2+m-1}(x) \\S_{\{k_1,k_2,…,k_{m},k_{m+1}\}}(n)\approx f^{k_{m+1}+1}_{\omega\cdot 2+m-1}(x)\approx f_{\omega\cdot 2+m}(k_{m+1}+1)$$

Conclusion

So $M(n)=_nS(n)\approx f_{\omega\cdot2+n-1}(n+1)\approx f_{\omega\cdot3}(n-1)$

This doesn't even come close to the TREE function which outgrows $f_{\vartheta(\Omega^\omega\omega)}(n)$

Answer 2

I concur with fejfo that $M(n) \approx f_{\omega \cdot 3}(n)$.

Letting $g(n) = S_{\{n\}}(n)$, we have $S_{\{n,1\}}(n) = S_{\{S_{\{n\}}(n)\}}(n) < g^2(n)$. Similarly, if $h(n) = S_{\{n,1\}}(n)$ then $S_{\{n,2\}}(n) = S_{\{S_{\{n,1\}}(n),1\}}(n) < h^2(n) < g^4(n)$. In general, $S_{\{n,m\}}(n) < g^{2^m}(n)$, and $S_{\{n,n\}}(n) < g^{2^n}(n)$. Since $g(n) < f_{\omega \cdot 2}(n)$, $S_{\{n,n\}}(n) < f_{\omega \cdot 2 + 1}(2^n)$.

The same thing happens with the third variable - if $g(n) = S_{\{n,n\}}(n)$, then $S_{\{n,n,n\}}(n) < g^{2^n}(n)$, and so $S_{\{n,n,n\}}(n) \approx f_{\omega \cdot 2 + 2}(2^n)$. ($2^n$ is so much more slowly growing than $f_{\omega \cdot 2 + 1}$ that its effect is imperceptible.) More generally, $S_{\{n,n,\ldots,n\}}(n) \approx f_{\omega \cdot 2 + k-1}(2^n)$, where $k$ is the number if $n$'s in the array. So $M(n) < f_{\omega \cdot 3}(n)$.