The next few exercises refer to the algorithms in Figure 6.43, both which solve the same problem 1. Give and solve (using induction) a recurrence relation for the running time of f 2. Give a...

The next few exercises refer to the algorithms in Figure 6.43, both which solve the same problem

1. Give and solve (using induction) a recurrence relation for the running time of f

2. Give a recurrence relation for g, and use it to prove that g(n) runs in O(log2 n) time.

3. Describe the set of input values n that cause the worst-case behavior for g(n)

4. What problem do f and g solve? Prove your answer.

Figure 6.43: Two algorithms.