1. The recursive Fibonacci function makes approximately a n2 recursive calls for problems of a large size n b 2n recursive calls for problems of a large size n 2. Each level in a completely filled...

1. The recursive Fibonacci function makes approximately

a n²
recursive calls for problems of a large size n

b 2ⁿ
recursive calls for problems of a large size n

2. Each level in a completely filled binary call tree has

a twice as many calls as the level above it

b the same number of calls as the level above it

3. A linear search of a sorted list can halt when the target is less than a given element in the list. Define a modified version of this algorithm and state the computational complexity, using big-O notation, of its best-, worst-, and average-case performances.