Is there a "largest function"?

Question

In one of my classes, the professor asked about what we think the largest function was. Many thought perhaps ${e^x}^{e^x}$, but I thought about $n!$

When I talk about a "largest function", I mean the function that increases the quickest.

The professor asked about a function larger than $n!$ to which I responded, $2n!$

Although snarky in nature, it is technically true.

So my question is this:

What is the "largest function" if we define "largest" as being "increases the quickest". A parent function is what we need, as it prevents someone like myself from putting a larger coefficient before the function.

Answer 1

Look into hyperoperators.

https://en.wikipedia.org/wiki/Hyperoperation

This is a sequence of binary operators, each generating larger numbers than the previous. Define $f_n(x) = n \uparrow^n x$. You now have an infinite sequence of functions, each one in the sequence grows faster than the previous one. And they will grow MUCH faster than $n!$.

Answer 2

There is none. Given any function from $\mathbb R$ to $\mathbb R$, it is not hard to construct another function that grows faster than it.

Answer 3

There is no largest function, any more than there is a largest number. Take the largest function you can think of, call its slope $f'(x)$. Now double that function - you have doubled your slope to $2f'(x)$.

Answer 4

There are many large functions, e.g. $e^n$, $n!$ etc.

And you might know that $e^n$ grows faster than $n^k$ for any $k\geq 1$.

But there are other interesting functions, e.g. the Busy Beaver function. It asymtotically grows faster than any computable function. That means you cannot even write a computer program that produces a faster growing function.

The nice thing is: The busy beaver function is well-defined, but not computable:)! This function really gives an upper bound for the growth of computable functions (e.g., it grows much faster than any function that just contains hyperoperators or the TREE function).

edit: Of course, there are more and even faster growing functions.

Answer 5

Given a sequence of functions $f_i:\mathbb N \to \mathbb N$, let $f_\infty:\mathbb N \to \mathbb N$ be defined by $$f_\infty(n) = 1+\max\{f_1(n),f_2(n),\dotsc,f_n(n)\}$$ $f_\infty$ is eventually greater than any function in the sequence $f_i$.

Alternatively we can define $f_\infty$ by $$f_\infty(n)=1+\sum_{i=1}^nf_i(n)$$ This type of argument is called a diagonal argument.

Answer 6

Take a look at Hardy's translation and edition of Du Bois-Reymond's Orders of Infinity, page 10:

Answer 7

I remember that this one gets mighty big mighty fast: https://en.wikipedia.org/wiki/Ackermann_function

However whatever function you claim is the biggest, I can beat it by squaring it.

It is like trying to name the smallest positive number. Whatever number you claim is smallest, I can cut in half.

Answer 8

There is no 'largest' function, as one can always add, multiply, or exponentiate again to produce a larger one, there are some that get very large, very quickly. For example, the Ackermann function $A(x, y)$, which is defined as follows (for $x, y \geq 0$): $$ A(x,y) = \left\{ \begin{array}{ll1} x + 1 & \text{if }y=0 \\ A(x-1,1)&\text{if }x>0, y=0\\ A(x-1,A(x,y-1))&\text{if }x,y>0 \end{array} \right. $$ Powered by a recursive definition, this function grows astonishingly fast. For example, while $A(1, 1) = 3$ and $A(2, 2) = 7$, $A(3, 3) = 61$, $A(4, 4)$ is: $$2^{2^{2^{65536}}} - 3$$ and will overload most computers (to give an idea of scale, a computer with a 128 bit processor can handle numbers with about $40$ digits, and this is many, many times larger than that). And while this is an astoundingly large function, there are infinitely larger ones.

Answer 9

I'm just saying, the function that I think is the LARGEST ar aka the one that increases the value of the number is, what I invented, is Pxn("number").That kinda makes in infifnite because how it works for example if I took $1$, it would give me $\pi$, but if I take $3$, that means take every single number of $\pi$ and multiply it by $3$ so $``3.14"$ would be $``6.312"$. So there you go, bye (I wrote this and I'm 9yr old)