making algaristhisms

Question 1

substitution method,

Answer 1

In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct.

Question 2

recursion-tree method

Answer 2

converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.

Question 3

master method

Answer 3

The master method provides bounds for recurrences of the form
T .n/ DaT .n=b/ Cf .n/ ; (4.2)
where a 1, b>1,and f .n/ is a given function. Such recurrences arise frequently. A recurrence of the form in equation (4.2) characterizes a divideand-conquer algorithm that creates a subproblems, each of which is 1=b the size of the original problem, and in which the divide and combine steps together take f .n/ time.

To use the master method, you will need to memorize three cases, but once you do that, you will easily be able to determine asymptotic bounds for many simple recurrences. We will use the master method to determine the running times of the divide-and-conquer algorithms for the maximum-subarray problem and for matrix multiplication, as well as for other algorithms based on divideand-conquer elsewhere in this book

Question 4

brute-force

Answer 4

try all combos

Question 5

A transformation

Answer 5

find a sequence of days over which the net change from the first day to the last is maximum. Instead of looking at the daily prices, let us instead consider the daily change in price, where the change on day i is the difference between the prices after day i -1 and after day i.