Data structures and algorithms I actually used while working at tech companies

Re:Data structures and algorithms I actually used while work... by WJW on Wednesday July 15, 2020 @07:36AM (#23843781)

The closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-com.... It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU.

There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.

[ Parent | on HN ]

Re:Data structures and algorithms I actually used while work... by Taek on Wednesday July 15, 2020 @10:09AM (#23845428)

Technically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result.

That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.

[ Parent | on HN ]