Java Reference
In-Depth Information
(a) c
1
n
(b) c
2
n
3
+ c
3
(c) c
4
n log n + c
5
n
(d) c
6
2
n
+ c
7
n
6
3.9 (a) What is the smallest integer k such that
p
n = O(n
k
)?
(b) What is the smallest integer k such that n log n = O(n
k
)?
3.10 (a) Is 2n = (3n)? Explain why or why not.
(b) Is 2
n
= (3
n
)? Explain why or why not.
3.11 For each of the following pairs of functions, either f(n) is in O(g(n)), f(n)
is in (g(n)), or f(n) = (g(n)). For each pair, determine which relation-
ship is correct. Justify your answer, using the method of limits discussed in
Section 3.4.5.
(a) f(n) = lo
g
n
2
; g(n) = log n + 5.
(b) f(n) =
p
n; g(n) = log n
2
.
(c) f(n) = log
2
n; g(n) = log n.
(d) f(n) = n; g(n) = log
2
n.
(e) f(n) = n log n + n; g(n) = log n.
(f) f(n) = log n
2
; g(n) = (log n)
2
.
(g) f(n) = 10; g(n) = log 10.
(h) f(n) = 2
n
; g(n) = 10n
2
.
(i) f(n) = 2
n
; g(n) = n log n.
(j) f(n) = 2
n
; g(n) = 3
n
.
(k) f(n) = 2
n
; g(n) = n
n
.
3.12 Determine for the following code fragments in the average case. Assume
that all variables are of type
int
.
(a)
a=b+c;
d=a+e;
(b)
sum=0;
for(i=0;i<3;i++)
for(j=0;j<n;j++)
sum++;
(c)
sum=0;
for(i=0;i<n
*
n;i++)
sum++;
(d)
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
tmp=AA[i][j];
AA[i][j]=AA[j][i];
AA[j][i]=tmp;
}
(e)
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j
*
=2)
sum++;
