Difference between revisions of "CSC212 Final Exam 2014"
| Line 27: | Line 27: | ||
<br /> | <br /> | ||
* Assume we want to compute the ''n''<sup>th</sup> term of a Fibonacci sequence, and do so '''recursively'''. | * Assume we want to compute the ''n''<sup>th</sup> term of a Fibonacci sequence, and do so '''recursively'''. | ||
| − | * Assume we | + | * Assume we have '''not''' precomputed the terms and stored them in an array, first. There are no arrays, no additional data structures used here. |
| − | * Assume we do not use any form of tail-end | + | * Assume we do not use any form of truncation of the tail-end recursion. |
| − | * | + | * In this case, what it the '''best''' complexity we can expect for computing recursively the ''n''<sup>th</sup> Fibonacci term, if we are very efficient in our coding? O(1), O(n log(n) ), O(n), O(n^2), O(2^n)? |
