O(f(n))指的是规模为n的计算问题，时间复杂度是f(n)，显然O(tree(n))大得不得了。R(6,6)只有100多，tree(3)用普通数学符号根本无法写。
估计你是想问R(n,n)和tree(n)有多难算吧？R(n,n)出名的难算，那是相对于它本身的大小来说的，怎么能和大数函数比？好比博尔特出名的爆发力强，但这个"强"能和火箭去比赛吗？何况大数函数的力量远远不止火箭，而是没人能想象，甚至科幻片开脑洞都编不出来的那种水平呢。我们考虑一下，对一个特定的数m，有m个人中，两个人相互认识的组合数C(m,2)<m^2。用m^2位的二进制数枚举这些情况，认识为1，不认识为0，最多只有2^m^2种。对每一种情况，枚举关系为1的情况，最多m^2对，然后每一对继续枚举关系为1的情况，最多m^2对，一直枚举到n层，最多m^(2n)次就能验证是否有n个人互相认识。互相不认识的情况同理，最后枚举次数不超过2*m^(2n)。于是对某个m，最多枚举2^(m^2+1)*m^2n次。然后m=R(n,n)<(2n)!<(2n)^(2n)，最后的总次数不超过2^((2n)^(4n)+1)*(2n)^(4n^2)，这个复杂度远小于2^2^n^2。也就是计算R(n,n)用最笨的穷举法，时间复杂度也远低于O(2^2^n^2)。
然后看看tree(n)。有什么时间复杂度最优的方法计算tree(n)，这很难分析，毕竟大数函数超越了我们能写出来的所有事物。但无论什么算法，时间复杂度总有一个下界，O(log(tree(n)))。这是因为算完后总要把答案输出来吧。一个n位数的大小大概在10^n左右，也就是说tree(n)的答案长度都长达log(tree(n))左右。事实上，从大数函数的尺度来看，O(log(tree(n)))和O(tree(n))几乎没有区别，可以直接用O(tree(n))估计。为什么我这么说呢，你想想，一亿层指数塔，取log后指数塔还有9999万9999层，没有减少太多。而常数层的指数塔还不到O(2↑↑n)呢，可是即使是O(2(一亿个↑)n)也不过是一个原始递归函数，哪能和tree函数比？
我们来看看O(tree(n))有多牛逼吧。令↑代表高德纳箭头，我们有O(2^2^n^3)<O(2^2^n^10)<O(2^2^2^n)<O(2^2^2^n^10)<O(2^2^2^2^n)<......<O(2↑↑n)<O(2↑↑2^n)<......<O(2↑↑2↑↑n)<......<O(2↑↑↑n)<O(2↑↑↑2↑↑n)<O(2↑↑↑2↑↑↑n)<......<O(2↑[4]n)<O(2↑[5]n)<.......<O(2↑[10^100]n)<.....<O(2↑[n]n)<......
走到这里，我们才刚刚超过了原始递归函数的极限，离O(tree(n))连沧海一粟都不算。下面为了加速，要引入(可数)无穷序数了。大数函数比自然数的数量多，需要用到无穷序数描述这些层级。ω=N是最小的无穷序数，我们定义2↑[ω]n=2↑[n]n。直观上来看，因为↑的数量n可以趋于无穷，超过任何固定的常数，用ω标记也很合理。然后和有限数量的↑一样，我们有2↑[ω+1]n=2↑[ω].......↑[ω]2，共n个2。对极限序数x(不存在a，使得x=a+1)，我们需要定义严格递增的序数"基本列"x[k]，其中k是自然数，x[k]的最小上界是x。然后有2↑[x]n=2↑[x[n]]n。为了保证对任意序数x>y，有O(2↑[x]n)>O(2↑[y]n)，对极限序数x≤ε0，我们定义一个"标准"的基本列如下:
设x=ω^a1+ω^a2+.......+ω^an，其中n∈N，a1≥a2≥.....≥an，我们有:
如果an=c+1，x[n]=ω^a1+ω^a2+.....+ω^c*n
如果an是极限序数，x[n]=ω^a1+ω^a2+.....+ω^an[n]
ε0[0]=1，ε0[n+1]=ω^ε0[n]
举例:2↑[ω^2]3=2↑[ω*3]3=2↑[ω*2+3]3
=2↑[ω*2+2]2↑[ω*2+2]2
=2↑[ω*2+2]4=.......
于是继续:O(2↑[ω]n)<O(2↑[ω+1]n)<......<O(2↑[ω*2]n)<O(2↑[ω*100]n)<O(2↑[ω^2]n)<O(2↑[ω^100]n)<O(2↑[ω^ω]n)<O(2↑[ω^ω^ω]n)<O(2↑[ω↑↑1000]n)<.......<O(2↑[ε0]n)
我们刚刚超过了皮亚诺算术可证的极限，离O(tree(n))比，仍然是沧海一粟都算不上。接下来要用到φ函数了，我们有ε0=φ(1,0)，ε5=φ(1,5)，εε0=φ(1,ε0)，εεε......=φ(2,0)等等，具体定义和基本列实在太复杂了，不写了。我们继续:
O(2↑[ε0]n)<O(2↑[ε0*5]n)<O(2↑[ε1]n)<O(2↑[εω]n)<O(2↑[εε0]n)<......<O(2↑[φ(2,0)]n)<O(2↑[φ(2,ε0)]n)<O(2↑[φ(3,0)]n)<......<O(2↑[φ(ε0,0)]n)<O(2↑[φ(φ(2,0),0)]n)<......<O(2↑[Γ0]n)
这里Γ0=φ(1,0,0)，增长率终于超过了ATR0可证的极限，但离O(tree(n))比，仍然非常遥远。我们继续:
O(2↑[Γ0]n)<O(2↑[φ(1,0,1)]n)<O(2↑[φ(1,1,0)]n)<O(2↑[φ(2,0,0)]n)<......<O(2↑[φ(1,0,0,0)]n)<......<O(2↑[SVO]n)
这里SVO=φ(1,0,0,0,......)，然后O(2↑[SVO]n)终于有了和O(tree(n))差不多级别的复杂度。你看看O(tree(n))是什么水平吧？
