Timeline for If the whole point of recursion is to break the problem into multiple smaller problems, what if those problems were solved in parallel?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17 at 0:04 | comment | added | gnasher729 | It's 1,5something ^ n. Which is absurdly bad for a problem that is easily solved in O(n) and with some maths and harder worker in O(log n) If you create a recursive function that returns both fib(n) and fib(n-1), that runs in O(n). | |
| S Sep 9, 2019 at 18:34 | history | suggested | PMah | CC BY-SA 4.0 |
Correct n^2 to 2^n, and formatted it
|
| Sep 9, 2019 at 16:15 | review | Suggested edits | |||
| S Sep 9, 2019 at 18:34 | |||||
| Sep 9, 2019 at 14:38 | comment | added | RiaD | It's not O(n^2), it's exponential | |
| May 5, 2019 at 18:39 | comment | added | Deduplicator |
And there is an even better approach using matrix-multiplication for O(log n) steps. If you don't just decide to simply pre-calculate every result fitting into a tiny int for O(1).
|
|
| May 5, 2019 at 17:00 | history | answered | Joe | CC BY-SA 4.0 |