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.

  • 1
    $\begingroup$ $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? $\endgroup$
    – k.stm
    Apr 3, 2014 at 11:21
  • 1
    $\begingroup$ Actually, $f(n)=n$ should be of linear computational complexity as you have to read in the data. $\endgroup$
    – Bill Trok
    Apr 3, 2014 at 11:25
  • 1
    $\begingroup$ well it could also be $\log(n)$ depending on how it's represented $\endgroup$ Apr 3, 2014 at 19:58
  • $\begingroup$ Ahh, yes I was mistaken. That is correct. $\endgroup$
    – Bill Trok
    Apr 3, 2014 at 21:04


You must log in to answer this question.

Browse other questions tagged .