Question

For each of the following recursive methods available on the class handout, derive a worst-case recurrence relation along with initial condition(s) and solve the relation to analyze the time complexity of the method. The time complexity must be given in a big-O notation.

1. digitSum(int n) - summing the digits of integer:

int digitSum(int n) {

                if (n < 10)

                                return n;

                return (digitSum(n/10) + n%10);

}

2. void reverseA(int l, int r) - reversing array:

void reverseA(int l, int r) {

                if (l < r) {

                                int t = A[l];

                                A[l] = A[r];

                                A[r] = t;

                                reverseA(l+1, r-1);

                }

}

Answer 1