C++ Programming Exercise: 1) A procedure with input n performs one major operati

Question

C++ Programming Exercise:

1) A procedure with input n performs one major operation then, if n > 0, calls itself recursively twice with input n - 1. Write the formula for the number of major operations in terms of n. (Assume n ? 0)

2) A procedure with input n performs one major operation then, if n > 1, calls itself twice with input n / 2. Write the formula for the number of major operations in terms of n. (For simplicity, assume n is exactly 2k where n ? 0.)

3) Implement a simple recursive Fibonacci function. That means the function returns fib(n) for n ?0 and does so using two recursive calls when n > 1. Then figure out an exact formula for the total number of calls when the function is called initially with input n.

Note: For the first two exercises, you do not need to code anything. Also, for the third exercise, for the formula part, you do not need to code anything.

Can someone give me the answers to these exercises?

Explanation / Answer

1. T(n) = T(n - 1) + T(n - 1) + 1

2. T(n) = 2T(n/2) + 2

3. // Fibonacci series

T(n) = T(n - 1) + T (n - 2) + 1

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.