Java Reference
In-Depth Information
Solve the following recurrences, which in all cases have
T
( 0 ) =
T
( 1 ) = 1.
A Big-Oh answer will suffice.
a.
7. 1 7
T
(
N
) =
T
(
N
/ 2 ) + 1
b.
T
(
N
) =
T
(
N
/ 2 ) +
N
T
(
N
) =
T
(
N
/ 2 ) +
N
2
c.
d.
T
(
N
) = 3
T
(
N
/ 2 ) +
N
T
(
N
) = 3
T
(
N
/ 2 ) +
N
2
e.
f.
T
(
N
) = 4
T
(
N
/ 2 ) +
N
T
(
N
) = 4
T
(
N
/ 2 ) +
N
2
g.
T
(
N
) = 4
T
(
N
/ 2 ) +
N
3
h.
Solve the following recurrences, which in all cases have
T
( 0 ) =
T
( 1 ) = 1.
A Big-Oh answer will suffice.
a.
7. 1 8
T
(
N
) =
T
(
N
/ 2 ) + log
N
b.
T
(
N
) =
T
(
N
/ 2 ) +
N
log
N
T
(
N
) =
T
(
N
/ 2 ) +
N
2
log
N
c.
d.
T
(
N
) = 3
T
(
N
/ 2 ) +
N
log
N
T
(
N
) = 3
T
(
N
/ 2 ) +
N
2
log
N
e.
f.
T
(
N
) = 4
T
(
N
/ 2 ) +
N
log
N
T
(
N
) = 4
T
(
N
/ 2 ) +
N
2
log
N
g.
T
(
N
) = 4
T
(
N
/ 2 ) +
N
3
log
N
h.
Solve the following recurrences, which in all cases have
T
( 0 ) = 1. A
Big-Oh answer will suffice.
a.
7. 1 9
T
(
N
) =
T
(
N
- 1 ) + 1
b.
T
(
N
) =
T
(
N
- 1 ) + log
N
c.
T
(
N
) =
T
(
N
- 1 ) +
N
d.
T
(
N
) = 2
T
(
N
- 1 ) + 1
e.
T
(
N
) = 2
T
(
N
- 1 ) + log
N
f.
T
(
N
) = 2
T
(
N
- 1 ) +
N
Strassen's algorithm for matrix multiplication multiplies two
N
×
N
7.20
matrices by performing seven recursive calls to multiply two
N
/2
×
N
/ 2 matrices. The additional overhead is quadratic. What is
the running time of Strassen's algorithm?
IN PRACTICE
7.21
Ackerman's function is defined as follows.
{
n
+ 1
if
m
= 0
A
(
m
,
n
) =
A
(
m
- 1, 1 )
if
m
> 0 and
n
= 0
A
(
m
- 1,
A
(
m
,
n
- 1 ) )
if
m
> 0 and
n
> 0
Implement Ackerman's function.
Search WWH ::
Custom Search