Simple, tail-recursive version of Fibonacci. Should run in nearly O(n).

fibonacci.js

var fibonacci = (function() {
    var fib = function(curr, next, n) {
        return  (n === 0) ? curr : fib(next, curr + next, n - 1);
    };
    return function(n) {
        return fib(0, 1, n);
    }
}());