# Examples of functions which grow faster than their computational complexity.

A good example of this would be the function $f$ defined as follows, $f(n) = (10^n-1)$. While in this form it's equation is exponential, it is easy to note that $$f(n) = 99...9 \,(n \text{ times}).$$ Another example, at least in binary computer architecture, is the function $g(n)=2^n$, which can be computed with $n$ left binary shifts.

I realize that my examples makes use of rather trivial quirks of the way we represent numbers, but am curious if anyone has come across some nontrivial examples of this.

• $f(n) = n$ is of constant computational complexity, right? Isn’t it more interesting to ask for functions which grow slower than their computational complexity? Apr 3, 2014 at 11:21
• Actually, $f(n)=n$ should be of linear computational complexity as you have to read in the data. Apr 3, 2014 at 11:25
• well it could also be $\log(n)$ depending on how it's represented Apr 3, 2014 at 19:58
• Ahh, yes I was mistaken. That is correct. Apr 3, 2014 at 21:04