Daily Code Review - 2/11/19
Posted by Admin_Ray
12 months ago
Post your code snippets here to receive help or feedback.
1
12 months ago
What's a good way to solve the Fibonacci sequence with sub-linear time complexity?  I can write a brute-force solution easily enough, but O(n) when n is 10E20 isn't exactly efficient.  Below is my brute force solution.

function fibonacci(index) { // Assuming [1, 2, 3, 5... n]
	let first = 1;
	let second = 2;
	for (let i = 0; i < index; i ++) {
		var current = first + second;
		first = second;
		second = current;
		// We change the values iteratively so we only have to keep track of
		// the last two values.  The overall space complexity should be O(3).
	} return current;
}

Coding wizards, do your thing.
1
NUMBER FOLLOWERS
A community for programmers (or non-programmers) to come together and let out their inner nerd.

if (user.type === "programmer" || user.type === "normie") {
  console.log(`Welcome, ${user.username}!`);
}
COMMUNITY RULES
  • 1. Anything goes.
COMMUNITY MODERATORS
None