You do not have permission to delete messages in this group
Copy link
Report message
Show original message
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
Hello,
Could you explain the following?
"The tree-recursive Fibonacci computation requires theta(phi^n) steps
and space theta(n), where phi is the golden ratio described in
section 1.2.2." [1]
Why theta(phi^n), not theta(phi^n/sqrt5)?
How to check this?
Could you also comment on the Exercise 1.14?
"What are the orders of growth of the space and number of steps used
by this process as the amount to be changed increases?" [1]
Different sources have different opinions. [2, 3, 4]
The following line is not clear too:
"We say that R(n) has order of growth (f(n)), written R(n) = (f(n))
(pronounced ``theta of f(n)''), if there are positive constants k1 and
k2 independent of n such that http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-18.gif for any sufficiently large value of n." [1]
I'm not good at math. Where did we get these constants?