Answered You can hire a professional tutor to get the answer.
Consider the following recurrence equation. Note: The symbol is the "floor" function. For any real x, [x] rounds down x to its nearest integer. For...
Consider the following recurrence equation. Note: The symbol is the "floor" function. For any real x, [x] rounds down x to its nearest integer. For example, [3.1415] = 3. And [3] = 3.
f(n) = (1; n = 1; f([n/2]) + n; n 2)
(a) Compute and tabulate f(n) for n = 1 to 8. (Please show how you got the values for f(n))
(b) Prove by induction that the solution has the following bound.
f(n) < 2n Hint: A strong form of induction is needed here. (Don't try to increment n by 1 in your induction step.) To prove the bound for any n, you have to assume the bound is true for all smaller values of n. That is, assume f(m) < 2m for all m < n. This strong hypothesis in particular will mean f([n/2]) < 2[n/2].
