Data Structures, Algorithms, & Applications in Java
Chapter 3, Exercise 18
(a)
_________________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________________
public static int factorial(int n) 0 0 Theta(0)
{ 0 0 Theta(0)
if (n <= 1) return 1; 1 1 Theta(1)
else return n * factorial(n - 1); 1 + tfactorial(n-1) 1 1 + tfactorial(n-1)
} 0 0 Theta(0)
_________________________________________________________________________________________
So, tfactorial(n) = c for
n <= 1 and
1 + tfactorial(n-1) for
n > 1 (here c is a constant).
Using repeated substitution, we get:
tfactorial(n) = 1 + tfactorial(n-1)
= 2 + tfactorial(n-2)
= 3 + tfactorial(n-3)
.
.
.
= n - 1 + tfactorial(1)
= n - 1 + c
= Theta(n)
(c)
We shall do the analysis for the case n = a.length >=; 1.
_______________________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________________
public static MinMaxPair minMax(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (a.length < 1) 1 1 Theta(1)
throw ... 1 0 Theta(0)
MinMaxPair p = new MinMaxPair(0,0); 1 1 Theta(1)
for (int i = 1; i < a.length; i++) 1 Theta(n) Theta(n)
if (a[p.min].greaterThan(a[i])) p.min = i; 1 Theta(n) Theta(n)
else if (a[p.max].lessThan(a[i])) p.max = i; 1 Omega(0), O(n) Omega(0), O(n)
return p; 1 1 Theta(1)
} 0 0 Theta(0)
_______________________________________________________________________________________
So, tminMax(n) = Theta(n),
n >= 1.
(e)
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
public static void multiply(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 0; i < m; i++) 1 Theta(m) Theta(m)
for (int j = 0; j < p; j++) 1 Theta(mp) Theta(mp)
{ 0 0 Theta(0)
int sum = 0; 1 Theta(mp) Theta(mp)
for (int k = 0; k < n; k++) 1 Theta(mnp) Theta(mnp)
sum += a[i][k] * b[k][j]; 1 Theta(mnp) Theta(mnp)
c[i][j] = sum; 1 Theta(mp) Theta(mp)
} 0 0 Theta(0)
} 0 0 Theta(0)
_______________________________________________________________________________
So,
tmultiply(m, n, p) = Theta(mnp)
(g)
Let n = coeff.length.
Assume that n >= 1.
___________________________________________________________________________________
Statement s/e Frequency Total steps
___________________________________________________________________________________
public static Computable valueOf(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (coeff.length < 1) 1 1 Theta(1)
throw ... 1 0 Theta(0)
Computable y = (Computable) ...; 1 1 Theta(1)
for (int i = 1; i < coeff.length; i++) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
y = (Computable) y.multiply(x); 1 Theta(n) Theta(n)
// add in next term 0 0 Theta(0)
value.increment(y.multiply(coeff[i])); 1 Theta(n) Theta(n)
} 0 0 Theta(0)
return value; 1 1 Theta(1)
} 0 0 Theta(0)
___________________________________________________________________________________
So,
tvalueOf (n) = Theta(n), n >= 1.
(i)
Let n = a.length.
Assume that r.length >= a.length.
__________________________________________________________________________________________
Statement s/e Frequency Total steps
__________________________________________________________________________________________
public static void rank(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (r.length < a.length) 1 1 Theta(1)
throw ...
for (int i = 0; i < a.length; i++) 1 Theta(n) Theta(n)
r[i] = 0; 1 Theta(n) Theta(n)
for (i = 1; i < a.length; i++) 1 Theta(n) Theta(n)
for (int j = 0; j < i; j++) 1 Theta(n2) Theta(n2)
if (a[j].lessThanOrEqual(a[i])) r[i]++; 1 Theta(n2) Theta(n2)
else r[j]++; 1 Omega(0), O(n2) Omega(0), O(n2)
} 0 0 Theta(0)
__________________________________________________________________________________________
So,
trank (n) = Theta(n2),
when
r.length >= a.length.
(k)
Let n = a.length.
________________________________________________________________________________
Statement s/e Frequency Total steps
________________________________________________________________________________
public static void selectionSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int size = a.length; size > 1; size--) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
int j = MyMath.max(a, size-1); Theta(size) Theta(n) Theta(n2)
MyMath.swap(a, j, size - 1); 1 Theta(n) Theta(n)
} 0 0 Theta(0)
} 0 0 Theta(0)
________________________________________________________________________________
So, tselectionSort (n) = Theta(n2)
(m)
First, we obtain the asymptotic complexity of
Insert.insert.
For the analysis, we shall assume that
= a.length <
n + 1.
_________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________
public static void insert(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (a.length < n + 1) 1 1 Theta(1)
throw ... 1 0 Theta(0)
int i; 0 0 Theta(0)
for (i = n - 1; i >= 0 && ...) 1 Omega(1), O(n) Omega(1), O(n)
a[i+1] = a[i]; 1 Omega(1), O(n) Omega(1), O(n)
a[i+1] = x; 1 1 Theta(1)
} 0 0 Theta(0)
_________________________________________________________________________________
So,
tinsert(n) = Omega(1), O(n)
Now, we analyze the method insertionSort.
Let n = a.length.
____________________________________________________________________________________
Statement s/e Frequency Total steps
____________________________________________________________________________________
public static void insertionSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 1; i < a.length; i++) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
Insert.insert(a, i, t); Omega(1), O(i) Theta(n) Omega(n), O(n2)
} 0 0 Theta(0)
} 0 0 Theta(0)
____________________________________________________________________________________
So,
tinsertionSort (n) = Omega(n), O(n2)
(o)
First, we obtain the asymptotic complexity of
bubble.
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
public static void bubble(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 0; i < n - 1; i++) 1 Theta(n) Theta(n)
if (a[i].greaterThan(a[i+1])) 1 Theta(n) Theta(n)
MyMath.swap(a, i, i + 1); 1 Omega(0), O(n) Omega(0), O(n)
} 0 0 Theta(0)
_______________________________________________________________________________
So,
tbubble (n) = Theta(n)
Now, we analyze the method bubbleSort.
Let n = a.length.
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
_
public static void bubbleSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = a.length; i > 1; i--) 1 Theta(n) Theta(n)
bubble(a, i); Theta(i) Theta(n) Theta(n2)
} 0 0 Theta(0)
So,
tbubbleSort (n) = Theta(n2)