|
Your solution is quadratic. Fibonacci numbers grow geometrically and bignum arithmetic is linear in the number of digits for addition. Unless you have access to an ALU that can do unbounded integer arithmetic in constant time? Fibonacci is a dumb interview problem and your answers are probably wrong too. FamDav fucked around with this message at 20:24 on Apr 16, 2016 |
#
¿
Apr 16, 2016 20:18
|
|
|
|
| # ¿ May 10, 2024 02:07 |
|
|
Walh Hara posted:Ha, fair point, my example is wrong (but my claim that there are ways to calculate fibonacci in linear time is not). Either way I was just pointing out that when people say "solve fibo with recursion" you do not necessarily have to answer with fibo(n) = fibo(n-1) + fibo(n-2). Whether you use recursion or iteration shouldn't really change the time complexity (big O) of the optimal solution of any problem if you know what you're doing. There is no known linear time algorithm for Fibonacci that doesn't assume a machine that we cannot build. The best known is n log n off the top of my head, which takes advantage of matrix multiplication.
|
|
#
¿
Apr 16, 2016 21:25
|
|
|
Sex Bumbo posted:https://www.nayuki.io/page/fast-fibonacci-algorithms quote:(Note: This is counted in terms of the number of bigint arithmetic operations, not primitive fixed-width operations)
|
|
#
¿
Apr 16, 2016 23:03
|
|
|
I think the only time where I corrected an interviewer and it wasn't awful was telling him you can construct a heap from an arbitrary array in linear time after he said I was wrong. He was like really and I was like yeah and then I sketched it out and he was like oh cool good poo poo good poo poo.
|
|
#
¿
Jun 21, 2016 16:35
|
|
|
Why node vs Apache though
|
|
#
¿
Aug 11, 2016 03:46
|
|