Skip to content

Instantly share code, notes, and snippets.

@eduardolundgren
Created October 12, 2012 03:46
Show Gist options
  • Save eduardolundgren/3877188 to your computer and use it in GitHub Desktop.
Save eduardolundgren/3877188 to your computer and use it in GitHub Desktop.
Different algorithms to calculate Fibonacci number
// Fibonacci
// n = 1 2 3 4 5 6 7
// 1 1 2 3 5 8 13...
// O(K)
var fibc = function(n) {
var sqrt5 = Math.sqrt(5),
phi = (1 + sqrt5)*0.5;
return Math.round(Math.pow(phi, n)/sqrt5);
};
// O(N)
var fibn = function(n) {
if (n < 1) {
return 0;
}
var i = 0,
j = 1,
k = 1;
for (; k < n; k++) {
j += i;
i = j - i;
}
return j;
};
// O(Nˆ2)
var fibr = function(n) {
if (n <= 2) {
return 1;
}
return fib(n - 2) + fib(n - 1);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment