Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

Just No more free questions left!

Upgrade Now

Write a method fib that a takes an integer n and returns the nth Fibonacci number.

Let's say our Fibonacci series is 0-indexed and starts with 0. So:

fib(0); // => 0 fib(1); // => 1 fib(2); // => 1 fib(3); // => 2 fib(4); // => 3 ...

Our solution runs in n time.

There's a clever, more mathy solution that runs in time, but we'll leave that one as a bonus.

If you wrote a recursive method, think carefully about what it does. It might do repeat work, like computing fib(2) multiple times!

We can do this in space. If you wrote a recursive method, there might be a hidden space cost in the call stack!

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

time and space.

  • If you're good with matrix multiplication you can bring the time cost down even further, to . Can you figure out how?
  • If you're familiar with Binet's formula, then you can calculate any Fibonacci number in . Can you implement that?

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

Powered by qualified.io

. . .