Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

SICP: orders of growth

31 views
Skip to first unread message

.

unread,
May 30, 2012, 8:53:58 PM5/30/12
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?

[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.3
[2] http://sicp.org.ua/sicp/Exercise1-14
[3] http://community.schemewiki.org/?sicp-ex-1.14
[4] http://www.kendyck.com/archives/2005/04/25/solution-to-sicp-exercise-114/

Thanks
0 new messages