Data Structures, Algorithms, & Applications in C++
Chapter 3, Exercise 18
(a)
_________________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________________
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 >= 1.
_______________________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________________
bool minmax(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (n < 1) return false; 1 1 Theta(1)
indexOfMin = indexOfMax = 0; 1 1 Theta(1)
for (int i = 1; i < n; i++) 1 Theta(n) Theta(n)
if (a[indexOfMin] > a[i]) indexOfMin = i; 1 Theta(n) Theta(n)
else if (a[indexOfMax] ...) indexOfMax = i; 1 Omega(0), O(n) Omega(0), O(n)
return true; 1 1 Theta(1)
} 0 0 Theta(0)
_______________________________________________________________________________________
So, tminmax(n) = Theta(n),
n >= 1.
(f)
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
void matrixMultiply(...) 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)
T 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)
(h)
Assume that n >= 1.
___________________________________________________________________________________
Statement s/e Frequency Total steps
___________________________________________________________________________________
T polyEval(...) 0 0 Theta(0)
{ 0 0 Theta(0)
T y = 1, ...; 1 1 Theta(1)
for (int i = 1; i <= n; i++) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
y *= x; 1 Theta(n) Theta(n)
value += y * coeff[i]; 1 Theta(n) Theta(n)
} 0 0 Theta(0)
return value; 1 1 Theta(1)
} 0 0 Theta(0)
___________________________________________________________________________________
So,
tpolyEval (n) = Theta(n), n >= 1.
(j)
__________________________________________________________________________________________
Statement s/e Frequency Total steps
__________________________________________________________________________________________
void rank(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 0; i < n; i++) 1 Theta(n) Theta(n)
r[i] = 0; 1 Theta(n) Theta(n)
for (i = 1; i < n; i++) 1 Theta(n) Theta(n)
for (int j = 0; j < i; j++) 1 Theta(n2) Theta(n2)
if (a[j] <= 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).
(l)
________________________________________________________________________________
Statement s/e Frequency Total steps
________________________________________________________________________________
void selectionSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int size = n; size > 1; size--) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
int j = indexOfMax(a, size); Theta(size) Theta(n) Theta(n2)
swap(a[j], a[size - 1]); 1 Theta(n) Theta(n)
} 0 0 Theta(0)
} 0 0 Theta(0)
________________________________________________________________________________
So, tselectionSort (n) = Theta(n2)
(n)
First, we obtain the asymptotic complexity of
insert.
_________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________
void insert(...) 0 0 Theta(0)
{ 0 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 function insertionSort.
____________________________________________________________________________________
Statement s/e Frequency Total steps
____________________________________________________________________________________
void insertionSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 1; i < n; i++) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
T t = a[i]; 1 Theta(n) Theta(n)
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)
(p)
First, we obtain the asymptotic complexity of
bubble.
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
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)
swap(a[i], a[i + 1]); 1 Omega(0), O(n) Omega(0), O(n)
} 0 0 Theta(0)
_______________________________________________________________________________
So,
tbubble (n) = Theta(n)
Now, we analyze the function bubbleSort.
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
_
void bubbleSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = n; 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)