1.15 Exercise 1.15

When evaluating (sine 12.15), the expression expands as follows:

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))

p is evaluated five times.

Since the angle is divided by a constant factor, the number of calls to p increases linearly with the angle. And since p does a constant amount of work, we can conclude that sine is O(n) in time. (Similar reasoning can show that it is also O(n) in space, with the stack frame growing as the number of calls to p does).

← prev up next →

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

1.1	Exercise 1.1
1.2	Exercise 1.2
1.3	Exercise 1.3
1.4	Exercise 1.4
1.5	Exercise 1.5
1.6	Exercise 1.6
1.7	Exercise 1.7
1.8	Exercise 1.8
1.9	Exercise 1.9
1.10	Exercise 1.10
1.11	Exercise 1.11
1.12	Exercise 1.12
1.13	Exercise 1.13
1.14	Exercise 1.14
1.15	Exercise 1.15
1.16	Exercise 1.16
1.17	Exercise 1.17
1.18	Exercise 1.18
1.19	Exercise 1.19
1.20	Exercise 1.20
1.21	Exercise 1.21
1.22	Exercise 1.22
1.23	Exercise 1.23
1.24	Exercise 1.24
1.25	Exercise 1.25
1.26	Exercise 1.26
1.27	Exercise 1.27
1.28	Exercise 1.28
1.29	Exercise 1.29
1.30	Exercise 1.30
1.31	Exercise 1.31
1.32	Exercise 1.32
1.33	Exercise 1.33
1.34	Exercise 1.34
1.35	Exercise 1.35
1.36	Exercise 1.36
1.37	Exercise 1.37
1.38	Exercise 1.38
1.39	Exercise 1.39
1.40	Exercise 1.40
1.41	Exercise 1.41
1.42	Exercise 1.42
1.43	Exercise 1.43
1.44	Exercise 1.44
1.45	Exercise 1.45
1.46	Exercise 1.46