3.57 Exercise 3.57

When computing fibs using the definition presented earlier, one addition is performed for each value of the stream besides the first two. This is because values of the stream aren’t calculated multiple times – in other words, because the delay special form memoizes values. If this were not the case, then the situation would be much different:

(stream-ref fibs 2) would need to perform one addition
(stream-ref fibs 3) would need to perform two additions: One for the last value in fibs and one more
(stream-ref fibs 4) would need to perform four additions: Two for the last value, one for the value before that, and one more
(stream-ref fibs 5) would need to perform seven additions: Four for the last value, two for the value before that, and one more
(stream-ref fibs 6) would need to perform twelve additions: Seven for the last value, four for the value before that, and one more

The growth in the number of additions is O(2^n). (This is not a tight bound, but the growth of the sequence is clearly exponential.)

← prev up next →

1	Chapter 1
2	Chapter 2
3	Chapter 3
4	Chapter 4
5	Chapter 5

3.1	Exercise 3.1
3.2	Exercise 3.2
3.3	Exercise 3.3
3.4	Exercise 3.4
3.5	Exercise 3.5
3.6	Exercise 3.6
3.7	Exercise 3.7
3.8	Exercise 3.8
3.9	Exercise 3.9
3.10	Exercise 3.10
3.11	Exercise 3.11
3.12	Exercise 3.12
3.13	Exercise 3.13
3.14	Exercise 3.14
3.15	Exercise 3.15
3.16	Exercise 3.16
3.17	Exercise 3.17
3.18	Exercise 3.18
3.19	Exercise 3.19
3.20	Exercise 3.20
3.21	Exercise 3.21
3.22	Exercise 3.22
3.23	Exercise 3.23
3.24	Exercise 3.24
3.25	Exercise 3.25
3.26	Exercise 3.26
3.27	Exercise 3.27
3.28	Exercise 3.28
3.29	Exercise 3.29
3.30	Exercise 3.30
3.31	Exercise 3.31
3.32	Exercise 3.32
3.33	Exercise 3.33
3.34	Exercise 3.34
3.35	Exercise 3.35
3.36	Exercise 3.36
3.37	Exercise 3.37
3.38	Exercise 3.38
3.39	Exercise 3.39
3.40	Exercise 3.40
3.41	Exercise 3.41
3.42	Exercise 3.42
3.43	Exercise 3.43
3.44	Exercise 3.44
3.45	Exercise 3.45
3.46	Exercise 3.46
3.47	Exercise 3.47
3.48	Exercise 3.48
3.49	Exercise 3.49
3.50	Exercise 3.50
3.51	Exercise 3.51
3.52	Exercise 3.52
3.53	Exercise 3.53
3.54	Exercise 3.54
3.55	Exercise 3.55
3.56	Exercise 3.56
3.57	Exercise 3.57
3.58	Exercise 3.58
3.59	Exercise 3.59
3.60	Exercise 3.60
3.61	Exercise 3.61
3.62	Exercise 3.62
3.63	Exercise 3.63
3.64	Exercise 3.64
3.65	Exercise 3.65
3.66	Exercise 3.66
3.67	Exercise 3.67
3.68	Exercise 3.68
3.69	Exercise 3.69
3.70	Exercise 3.70
3.71	Exercise 3.71
3.72	Exercise 3.72
3.73	Exercise 3.73
3.74	Exercise 3.74
3.75	Exercise 3.75
3.76	Exercise 3.76
3.77	Exercise 3.77
3.78	Exercise 3.78
3.79	Exercise 3.79
3.80	Exercise 3.80
3.81	Exercise 3.81
3.82	Exercise 3.82