, SOLUTION MANUAL FOR Foundations of Algorithms Fifth Edition
Neapolitan
Important Notes
The file includes the complete test bank, organized chapter by chapter.
A sample of selected pages has been provided for preview.
All available appendices and Excel files (if included in the original resources) are
provided.
Quizzes, Midterm and final exams are included (if available in the original resources).
We continuously update our files to ensure you receive the latest and most accurate
editions.
New editions are added regularly – stay connected for updates!
⚠️Note on Answer Keys: If the answer key is not included within the chapter
questions, you will find the complete answers and solutions at the end of each
chapter.
✅ Why Buy From Us?
📚 Complete & organized chapter-by-chapter – no missing content, no guessing.
⚡ Instant digital delivery – get your file the moment you pay, no waiting.
📅 Always up to date – we track new editions so you always get the latest version.
💬 Friendly support – real humans ready to help, anytime you need us.
🔒 Safe & secure – thousands of satisfied students trust us every semester.
🛡️Our Guarantees
💰 Money-Back Guarantee: Not satisfied? We offer a full refund – no questions asked.
🔄 Wrong File? No Problem: Contact us and we will replace it immediately with the
correct version, free of charge.
⏰ 24/7 Support: We are always here – reach out anytime and expect a fast response.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.1
1) Write an algorithm that finds the largest number in a list (an array) of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: the maximum element in the list S
number findMax(int n, const keytype S[ ]) {
index i;
number max = S[1];
for(i =2; i<=n; i++)
if(S[i] > max)
max = S[i];
return max;
}
2) Write an algorithm that finds the m smallest numbers in a list of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n, empty list of numbers
Small indexed from 1 to m.
Output: the list Small with the smallest m numbers in it.
void find_m_Smallest(int n, const keytype S[ ], keytype Small[]) {
index i, j, k;
Small[1] = S[1];
for(i =2; i<=n; i++) {
if (j <=m)
find index j where S[i] needs to be inserted in Small, such that\
Small stays sorted in non-decreasing order;
for (k = m-1; k>=j, k--)
Small[k+1) = Small[k]; //shift right
Small[j] = Small[i]; //insert S[i]
}
}
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
3) Write an algorithm that prints out all the subsets of three elements of a set of n
elements. The elements of this set are stored in a list that is the input to the algorithm.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: none (the results are simply printed)
void nC3(int n, const keytype S[ ]) {
index i, j, k;
for (i =1; i<=n; i++)
for (j=i+1; j<=n;, j++)
for (k=j+1; k<=n; k++)
cout <<S[i] <<S[j] <<S[k] <<endl;
4) Write an Insertion Sort algorithm (Insertion Sort is discussed in Section 7.2) that
uses Binary Search to find the position where the next insertion should take place.
void insertionsort (int n, keytype S[]) {
index i , j ;
index &location
keytype x;
for (i = 2; i <= n; i++) {
x = S[ i ];
binsearch(i, S, x, location);
for (j=i-1; j>=location; j--)
S[ j + 1] = S[ j ]; //shift right
S[ j ] = x; //insert S[i] in final position
}
}
The function binsearch is the one in Algorithm 1.5, but modified so that, if the search is
unsuccessful, location is the index of the first element greater than x:
void binsearch (int n , const keytype S [ ] , keytype x , index& location) {
index low , high , mid ;
bool found = false
low = 1; hi gh = n; location = 0;
while ( low <= hi gh && !found) {
mid = ë(low + high)û/2 ;
if (x == S [mid ])
location = mid ;
elseif (x < S [mid ])
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
hi gh = mid 1;
else
low = mid + 1 ;
}
}
5) Write an algorithm that finds the greatest common divisor of two integers.
Input: two integers a and b
Output: the greatest common divisor of a and b
int gcd(int a, int b) {
if(b == 0)
return a;
return gcd(b, a%b) ;
}
6) Write an algorithm that finds both the smallest and largest numbers in a list of n
numbers. Try to find a method that does at most 1.5n comparisons of array items.
If we simply write one loop to find the minimum and one to find the maximum, there
will be 2(n-1) comparisons. We can reduce this number by comparing pairs of
numbers; this finds max(a,b) and min(a,b) in one comparison. Then we need only 2
more comparisons to update the overall min and max, for a total of 3 comparisons for
each pair of numbers. The total nr. of comparisons » 3n/2 = 1.5n.
7) Write an algorithm that determines whether or not an almost complete binary tree
is a heap.
Input: a pointer tree to an almost complete binary tree
Output: true if the input tree is a heap, false otherwise
bool isHeap(tree_pointer tree) {
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
if(tree->left == NULL && tree-> right == NULL)
return true;
if(tree->key < tree->left->key)
return false;
if(tree->right != NULL && tree->key < tree->right->key)
return false;
if(tree->right == null)
return isHeap(tree->left);
return isHeap(tree->left) && isHeap(tree->right);
}
Section 1.2
8) Under what circumstances, when a searching operation is needed, would Sequential
Search (Algorithm 1.1) not be appropriate?
If the data is already sorted and
there are a very large number of elements, or
the access to the elements is slow (e.g. they are on magnetic tape)
9) Give a practical example in which you would not use Exchange Sort (Algorithm 1.3)
to do a sorting task.
Is we had to sort an array of 10 million elements, the number of comparisons in
Exchange Sort would be » 107 x 107 = 1014. Even performing one comparison every
nanosecond, the program would still run for 105 seconds, which is more than one day.
A more efficient algorithm like Mergesort would run in less than half a second.
If we tried Exchange Sort algorithm for 100M elements, it would take almost 4 months,
whereas Mergesort would finish in about 5 seconds!
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.3
10) Define basic operations for your algorithms in Exercises 1-7, and study the
performance of these algorithms. If a given algorithm has an every-case time
complexity, determine it. Otherwise, determine the worst-case time complexity.
Exercise 1: Basic operation is comparison. Every-time count T(n)=n-1 .
Exercise 2: Basic operation is the assignment needed in the shift phase. Worst-case
count W(n,m) = n x m, if array is initially sorted in reverse order.
Exercise 3: Basic operation is accessing an array element. Every-time count T(n)=n(n-
1)(n-2).
Exercise 4: Basic operation is assigning an array element. Worst-case count W(n) = 3 +
4 + … + n = n(n+1)/2 -3, if array is initially sorted in reverse order.
Exercise 5: Basic operation is a%b, which is performed once per recursive call. Lamé
proved in 1844 that, when the initial numbers are Fibonacci numbers a = Fn+2, b = Fn+1,
then the algorithm will perform exactly n steps, so the worst case does not have a
closed-form for every number n.
Exercise 6: Basic operation is comparison. Every-time count T(n) = 3én/2ù.
Exercise 7: Basic operation is comparison. Worst-time count is 2 for every internal
node of the heap, which is » 2n/2 = n.
11) Determine the worst-case, average-case, and best-case time complexities for the
basic Insertion Sort and for the version given in Exercise 4, which uses Binary Search.
In this solution, we only count comparisons:
Basic Insertion Sort: B(n) = n (array already sorted), A(n) = n2/4, W(n) = n2/2 (array
reverse sorted). Proofs can be found in Section 7.2.
Insertion Sort with Binary Search: B(n) = 2lg n (each new key is always inserted in the
middle of the array, so only 2 comparisons are needed to find its location … if repeated
keys are allowed, than an array of identical elements only requires 1 comparison per
key!), A(n) = nlg n, W(n) = nlg n.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
12) Write a (n) algorithm that sorts n distinct integers, ranging in size between 1 and
kn inclusive, where k is a constant positive integer. (Hint: Use a kn-element array.)
Input: positive integer n, positive integer k, array of numbers S indexed from 1 to n
Output: sorted array S
void sort(int n, int S[]) {
int temp[] = int[k*n]; //initially all zeros
index i, j;
for(i=1; i<=n; i++) {
temp[S[i]] = x;
}
for(i=1, j=0; i<=k*n; i++) {
if(temp[i] != 0) {
a[j] = temp[i];
j++;
}
}
}
13) Algorithm A performs 10n2 basic operations, and algorithm B performs 300ln n
basic operations. For what value of n does algorithm B start to show its better
performance?
For n = 7, we have 490 operations in A, and 584 in B, so A is better, but for for n = 8, we
have 640 operations in A and 624 in B, so B is better (and stays that way for all n >= 8).
14) There are two algorithms called Alg1 and Alg2 for a problem of size n. Alg1 runs in
n2 microseconds and Alg2 runs in 100n log n microseconds. Alg1 can be implemented
using 4 hours of programmer time and needs 2 minutes of CPU time. On the other
hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If
programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute,
how many times must a problem instance of size 500 be solved using Alg2 in order to
justify its development cost?
For instance size n = 500, the problem is solved in 5005 x 10-6 = 25 x 104 x 10-6 = 0.25 s
with Alg1, and in 100 x 500 x log 500 x 10-6 = 0.1349 s with Alg2.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
The break-even point is found from this linear equation:
4*20 + 2*50 + y*0.25*50/60 = 15*20 + 6*50 + y*0.1349*50/60.
The solution is y =4379 times.
Section 1.4
15) Show directly that f(n) = n2 + 3n3 Î (n3). That is, use the definitions of O and to
show that f(n) is in both O(n3) and (n3).
We show that n2 + 3n3 Î O(n3) because for n³0,
n2 + 3n3 £ 4n3 ,
we can take c = 4, N = 0 to obtain our result.
We show that n2 + 3n3 Î W(n3) because for n³0,
n2 + 3n3 ³ 3n3 ,
we can take c = 3, N = 0 to obtain our result.
Thus, since n2 + 3n3 Î O(n3) and n2 + 3n3 Î W(n3), n2 + 3n3 Î Q(n3).
16) Using the definitions of O and , show that
6n2 + 20n Î O(n3), but 6n2 + 20n Ï n3).
Starting at N = 9, 6n2 + 20n < n3, so we can take c = 1, N = 9 in the definition of O.
On the other hand, no matter how large c were chosen, the limit c(6n2 + 20n)/n3 is
zero, so c(6n2 + 20n) cannot stay > n3which contradicts the definition of .
17) Using the Properties of Order in Section 1.4.2, show that
5n5 + 4n4 + 6n3 + 2n2 + n + 7 Î (n5).
Apply Property 7, with g(n) = n4 + 6n3/4 + 2n2/4 + n/4 + 7/4, h(n) = n5 , c = 4, and d =
5.
A direct proof is also possible: take f(n)= 5n5 + 4n4 + 6n3 + 2n2 + n + 7, and we have
5n5 + 4n4 + 6n3 + 2n2 + n + 7 <=5n5 + 4n4 + 6n3 + 2n2 + n + 7 <= 5n5 + 4 n5 + 6 n5 + 2
n5 + n5 + 7 n5
, Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
5n5<=5n5 + 4n4 + 6n3 + 2n2 + n + 7 <=25n5
Therefore the order will be Θ(n5), with c1=5 and c2=25, where n>=1.
18) Let p(n) = aknk + ak-1nk-1 + … + a1n + a0, where ak > 0. Using the Properties of Order
in Section 1.4.2, show that p(n) Î (n5).
As in Example 1.23, we repeatedly apply Properties 6 and 7 to show:
aknk Î (nk)
aknk + ak-1nk-1 Î (nk)
…
aknk + ak-1nk-1 + … + a1n + a0Î (nk)
As a technicality, if some of the lower-order coefficients ak-1, … a0 are ≤ 0, but in this
case we simply have a negative function aini, which is obviously in O(nk).
19) The function f(x) = 3n2+10n log n+1000n+4log n+9999 belongs in which of the
following complexity categories:
f(n) Î (n2), by repeatedly applying Properties 6 and 7 (or “throwing out” all the
lower-order terms).
20) The function f(x) = (log n)2 + 2n + 4n + log n + 50 belongs in which of the
following complexity categories:
f(n) Î (n), by repeatedly applying Properties 6 and 7 (or “throwing out” all the lower-
order terms).
Note: (log n)2 is not listed in Property 6, but we can apply Theorem 1.4 (L’Hȏpital’s
Rule) twice to show that lim[(log n)2/n] = lim2[(log n)/n] = lim[2/n] = 0, when n → ∞.
Now Theorem 1.3 ensures that (log n)2 Î (n).
Neapolitan
Important Notes
The file includes the complete test bank, organized chapter by chapter.
A sample of selected pages has been provided for preview.
All available appendices and Excel files (if included in the original resources) are
provided.
Quizzes, Midterm and final exams are included (if available in the original resources).
We continuously update our files to ensure you receive the latest and most accurate
editions.
New editions are added regularly – stay connected for updates!
⚠️Note on Answer Keys: If the answer key is not included within the chapter
questions, you will find the complete answers and solutions at the end of each
chapter.
✅ Why Buy From Us?
📚 Complete & organized chapter-by-chapter – no missing content, no guessing.
⚡ Instant digital delivery – get your file the moment you pay, no waiting.
📅 Always up to date – we track new editions so you always get the latest version.
💬 Friendly support – real humans ready to help, anytime you need us.
🔒 Safe & secure – thousands of satisfied students trust us every semester.
🛡️Our Guarantees
💰 Money-Back Guarantee: Not satisfied? We offer a full refund – no questions asked.
🔄 Wrong File? No Problem: Contact us and we will replace it immediately with the
correct version, free of charge.
⏰ 24/7 Support: We are always here – reach out anytime and expect a fast response.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.1
1) Write an algorithm that finds the largest number in a list (an array) of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: the maximum element in the list S
number findMax(int n, const keytype S[ ]) {
index i;
number max = S[1];
for(i =2; i<=n; i++)
if(S[i] > max)
max = S[i];
return max;
}
2) Write an algorithm that finds the m smallest numbers in a list of n numbers.
Input: positive integer n, list of numbers S indexed from 1 to n, empty list of numbers
Small indexed from 1 to m.
Output: the list Small with the smallest m numbers in it.
void find_m_Smallest(int n, const keytype S[ ], keytype Small[]) {
index i, j, k;
Small[1] = S[1];
for(i =2; i<=n; i++) {
if (j <=m)
find index j where S[i] needs to be inserted in Small, such that\
Small stays sorted in non-decreasing order;
for (k = m-1; k>=j, k--)
Small[k+1) = Small[k]; //shift right
Small[j] = Small[i]; //insert S[i]
}
}
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
3) Write an algorithm that prints out all the subsets of three elements of a set of n
elements. The elements of this set are stored in a list that is the input to the algorithm.
Input: positive integer n, list of numbers S indexed from 1 to n
Output: none (the results are simply printed)
void nC3(int n, const keytype S[ ]) {
index i, j, k;
for (i =1; i<=n; i++)
for (j=i+1; j<=n;, j++)
for (k=j+1; k<=n; k++)
cout <<S[i] <<S[j] <<S[k] <<endl;
4) Write an Insertion Sort algorithm (Insertion Sort is discussed in Section 7.2) that
uses Binary Search to find the position where the next insertion should take place.
void insertionsort (int n, keytype S[]) {
index i , j ;
index &location
keytype x;
for (i = 2; i <= n; i++) {
x = S[ i ];
binsearch(i, S, x, location);
for (j=i-1; j>=location; j--)
S[ j + 1] = S[ j ]; //shift right
S[ j ] = x; //insert S[i] in final position
}
}
The function binsearch is the one in Algorithm 1.5, but modified so that, if the search is
unsuccessful, location is the index of the first element greater than x:
void binsearch (int n , const keytype S [ ] , keytype x , index& location) {
index low , high , mid ;
bool found = false
low = 1; hi gh = n; location = 0;
while ( low <= hi gh && !found) {
mid = ë(low + high)û/2 ;
if (x == S [mid ])
location = mid ;
elseif (x < S [mid ])
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
hi gh = mid 1;
else
low = mid + 1 ;
}
}
5) Write an algorithm that finds the greatest common divisor of two integers.
Input: two integers a and b
Output: the greatest common divisor of a and b
int gcd(int a, int b) {
if(b == 0)
return a;
return gcd(b, a%b) ;
}
6) Write an algorithm that finds both the smallest and largest numbers in a list of n
numbers. Try to find a method that does at most 1.5n comparisons of array items.
If we simply write one loop to find the minimum and one to find the maximum, there
will be 2(n-1) comparisons. We can reduce this number by comparing pairs of
numbers; this finds max(a,b) and min(a,b) in one comparison. Then we need only 2
more comparisons to update the overall min and max, for a total of 3 comparisons for
each pair of numbers. The total nr. of comparisons » 3n/2 = 1.5n.
7) Write an algorithm that determines whether or not an almost complete binary tree
is a heap.
Input: a pointer tree to an almost complete binary tree
Output: true if the input tree is a heap, false otherwise
bool isHeap(tree_pointer tree) {
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
if(tree->left == NULL && tree-> right == NULL)
return true;
if(tree->key < tree->left->key)
return false;
if(tree->right != NULL && tree->key < tree->right->key)
return false;
if(tree->right == null)
return isHeap(tree->left);
return isHeap(tree->left) && isHeap(tree->right);
}
Section 1.2
8) Under what circumstances, when a searching operation is needed, would Sequential
Search (Algorithm 1.1) not be appropriate?
If the data is already sorted and
there are a very large number of elements, or
the access to the elements is slow (e.g. they are on magnetic tape)
9) Give a practical example in which you would not use Exchange Sort (Algorithm 1.3)
to do a sorting task.
Is we had to sort an array of 10 million elements, the number of comparisons in
Exchange Sort would be » 107 x 107 = 1014. Even performing one comparison every
nanosecond, the program would still run for 105 seconds, which is more than one day.
A more efficient algorithm like Mergesort would run in less than half a second.
If we tried Exchange Sort algorithm for 100M elements, it would take almost 4 months,
whereas Mergesort would finish in about 5 seconds!
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
Section 1.3
10) Define basic operations for your algorithms in Exercises 1-7, and study the
performance of these algorithms. If a given algorithm has an every-case time
complexity, determine it. Otherwise, determine the worst-case time complexity.
Exercise 1: Basic operation is comparison. Every-time count T(n)=n-1 .
Exercise 2: Basic operation is the assignment needed in the shift phase. Worst-case
count W(n,m) = n x m, if array is initially sorted in reverse order.
Exercise 3: Basic operation is accessing an array element. Every-time count T(n)=n(n-
1)(n-2).
Exercise 4: Basic operation is assigning an array element. Worst-case count W(n) = 3 +
4 + … + n = n(n+1)/2 -3, if array is initially sorted in reverse order.
Exercise 5: Basic operation is a%b, which is performed once per recursive call. Lamé
proved in 1844 that, when the initial numbers are Fibonacci numbers a = Fn+2, b = Fn+1,
then the algorithm will perform exactly n steps, so the worst case does not have a
closed-form for every number n.
Exercise 6: Basic operation is comparison. Every-time count T(n) = 3én/2ù.
Exercise 7: Basic operation is comparison. Worst-time count is 2 for every internal
node of the heap, which is » 2n/2 = n.
11) Determine the worst-case, average-case, and best-case time complexities for the
basic Insertion Sort and for the version given in Exercise 4, which uses Binary Search.
In this solution, we only count comparisons:
Basic Insertion Sort: B(n) = n (array already sorted), A(n) = n2/4, W(n) = n2/2 (array
reverse sorted). Proofs can be found in Section 7.2.
Insertion Sort with Binary Search: B(n) = 2lg n (each new key is always inserted in the
middle of the array, so only 2 comparisons are needed to find its location … if repeated
keys are allowed, than an array of identical elements only requires 1 comparison per
key!), A(n) = nlg n, W(n) = nlg n.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
12) Write a (n) algorithm that sorts n distinct integers, ranging in size between 1 and
kn inclusive, where k is a constant positive integer. (Hint: Use a kn-element array.)
Input: positive integer n, positive integer k, array of numbers S indexed from 1 to n
Output: sorted array S
void sort(int n, int S[]) {
int temp[] = int[k*n]; //initially all zeros
index i, j;
for(i=1; i<=n; i++) {
temp[S[i]] = x;
}
for(i=1, j=0; i<=k*n; i++) {
if(temp[i] != 0) {
a[j] = temp[i];
j++;
}
}
}
13) Algorithm A performs 10n2 basic operations, and algorithm B performs 300ln n
basic operations. For what value of n does algorithm B start to show its better
performance?
For n = 7, we have 490 operations in A, and 584 in B, so A is better, but for for n = 8, we
have 640 operations in A and 624 in B, so B is better (and stays that way for all n >= 8).
14) There are two algorithms called Alg1 and Alg2 for a problem of size n. Alg1 runs in
n2 microseconds and Alg2 runs in 100n log n microseconds. Alg1 can be implemented
using 4 hours of programmer time and needs 2 minutes of CPU time. On the other
hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If
programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute,
how many times must a problem instance of size 500 be solved using Alg2 in order to
justify its development cost?
For instance size n = 500, the problem is solved in 5005 x 10-6 = 25 x 104 x 10-6 = 0.25 s
with Alg1, and in 100 x 500 x log 500 x 10-6 = 0.1349 s with Alg2.
,Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
The break-even point is found from this linear equation:
4*20 + 2*50 + y*0.25*50/60 = 15*20 + 6*50 + y*0.1349*50/60.
The solution is y =4379 times.
Section 1.4
15) Show directly that f(n) = n2 + 3n3 Î (n3). That is, use the definitions of O and to
show that f(n) is in both O(n3) and (n3).
We show that n2 + 3n3 Î O(n3) because for n³0,
n2 + 3n3 £ 4n3 ,
we can take c = 4, N = 0 to obtain our result.
We show that n2 + 3n3 Î W(n3) because for n³0,
n2 + 3n3 ³ 3n3 ,
we can take c = 3, N = 0 to obtain our result.
Thus, since n2 + 3n3 Î O(n3) and n2 + 3n3 Î W(n3), n2 + 3n3 Î Q(n3).
16) Using the definitions of O and , show that
6n2 + 20n Î O(n3), but 6n2 + 20n Ï n3).
Starting at N = 9, 6n2 + 20n < n3, so we can take c = 1, N = 9 in the definition of O.
On the other hand, no matter how large c were chosen, the limit c(6n2 + 20n)/n3 is
zero, so c(6n2 + 20n) cannot stay > n3which contradicts the definition of .
17) Using the Properties of Order in Section 1.4.2, show that
5n5 + 4n4 + 6n3 + 2n2 + n + 7 Î (n5).
Apply Property 7, with g(n) = n4 + 6n3/4 + 2n2/4 + n/4 + 7/4, h(n) = n5 , c = 4, and d =
5.
A direct proof is also possible: take f(n)= 5n5 + 4n4 + 6n3 + 2n2 + n + 7, and we have
5n5 + 4n4 + 6n3 + 2n2 + n + 7 <=5n5 + 4n4 + 6n3 + 2n2 + n + 7 <= 5n5 + 4 n5 + 6 n5 + 2
n5 + n5 + 7 n5
, Chapter 1: Algorithms: Efficiency, Analysis, and Order Solutions
5n5<=5n5 + 4n4 + 6n3 + 2n2 + n + 7 <=25n5
Therefore the order will be Θ(n5), with c1=5 and c2=25, where n>=1.
18) Let p(n) = aknk + ak-1nk-1 + … + a1n + a0, where ak > 0. Using the Properties of Order
in Section 1.4.2, show that p(n) Î (n5).
As in Example 1.23, we repeatedly apply Properties 6 and 7 to show:
aknk Î (nk)
aknk + ak-1nk-1 Î (nk)
…
aknk + ak-1nk-1 + … + a1n + a0Î (nk)
As a technicality, if some of the lower-order coefficients ak-1, … a0 are ≤ 0, but in this
case we simply have a negative function aini, which is obviously in O(nk).
19) The function f(x) = 3n2+10n log n+1000n+4log n+9999 belongs in which of the
following complexity categories:
f(n) Î (n2), by repeatedly applying Properties 6 and 7 (or “throwing out” all the
lower-order terms).
20) The function f(x) = (log n)2 + 2n + 4n + log n + 50 belongs in which of the
following complexity categories:
f(n) Î (n), by repeatedly applying Properties 6 and 7 (or “throwing out” all the lower-
order terms).
Note: (log n)2 is not listed in Property 6, but we can apply Theorem 1.4 (L’Hȏpital’s
Rule) twice to show that lim[(log n)2/n] = lim2[(log n)/n] = lim[2/n] = 0, when n → ∞.
Now Theorem 1.3 ensures that (log n)2 Î (n).
