Chapter 3: Q69E (page 218)
Show that if f1(x) is O(g(x)) and f2(x) is o(g(x)), then f1(x) + f2(x) is O(g(x)).
f1(x) + f2(x) = O(g(x)).
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. Specify the steps of this algorithm.
How many comparisons does the insertion sort use to sort the list n, n – 1,…, 2, 1?
The binary insertion sort is a variation of the insertion sort that uses a binary search technique (see Exercise 44) rather than a linear search technique to insert the element in the correct place among the previously sorted elements.
Describe an algorithm that uses only assignment statements that replaces the triple (x, y, z)with (y, z, x). What is the minimum number of assignment statements needed?
Devise an algorithm to compute xn, where xis a real number and nis an integer. [Hint:First give a procedure for computing xnwhen nis nonnegative by successive multiplication by x, starting with 1. Then extend this procedure, and use the fact that x−n=1/xnto compute xnwhen nis negative.]
Describe an algorithm that takes an input a list of integers and finds the number of negative integers in the list.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
