Java Reference
In-Depth Information
Question 7
What is the Big Oh of the method
sumOf
given in Segment 7.12?
Question 8
Computing
x
n
for some real number
x
and an integral power
n
≥ 0 has a simple
recursive solution:
x
n
=
x
x
n
- 1
x
0
=
1
a.
What recurrence relation describes this algorithm's time requirement?
b.
By solving this recurrence relation, find the Big Oh of this algorithm.
We can compute
x
n
for some real number
x
and an integral power
n
0 more efficiently than the
approach that Question 8 suggests. To reduce the number of recursive calls and therefore the num-
ber of multiplications, we can express
x
n
as follows:
x
n
=
(
x
n
/2
)
2
when
n
is even and positive
x
n
=
x
(
x
(
n
- 1)/2
)
2
when
n
is odd and positive
x
0
=
1
≥
This computation could be implemented by a method
power(x,
n)
that contains the recursive call
power(x,
n/2)
. Since integer division in Java truncates its result, this call is appropriate regardless
of whether
n
is even or odd. Thus,
power(x,
n)
would invoke
power(x,
n/2)
once, square the
result, and, if
n
is odd, multiply the square by
x
. These multiplications are O(1) operations. Thus,
the execution time for
power(x,
n)
is proportional to the number of recursive calls.
The recurrence relation that represents the number of recursive calls and, therefore, the
method's time requirement to compute
x
n
is then
t
(
n
)
=
1
+
t
(
n
/
2) when
n
≥
2
t
(1)
=
1
t
(0)
=
1
Again,
n
/
2 truncates to an integer.
7.26
Since the recurrence relation involves
n
/
2, let's choose a power of 2—such as 16—as
n
's initial
value. We then write the following sequence of equations:
t
(16)
=
1
+
t
(8)
t
(8)
=
1
+
t
(4)
t
(4)
=
1
+
t
(2)
t
(2)
=
1
+
t
(1)
By substituting repeatedly, we get the following:
t
(16)
=
1
+
t
(8)
=
1
+
(1
+
t
(4))
=
2
+
(1
+
t
(2))
=
3
+
(1
+
t
(1))
=
4
+
t
(1)
Since 16
=
2
4
, 4
=
log
2
16. This fact, together with the base case
t
(1)
=
1, leads us to guess that
t
(
n
)
=
1
+
log
2
n
7.27
Now we need to prove that this guess is, in fact, true for
n
≥
1. It is true for
n
=
1, because
t
(1)
=
1
+
log
2
1
=
1
For
n
>
1, we know that the recurrence relation for
t
(
n
)
t
(
n
)
=
1
+
t
(
n
/
2)
is true. Remember that
n
/
2 truncates to an integer.
