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.