Perform complexity analysis for the algorithm by

1) find the recurrence equation;

(2) solve the recurrent equation and

(3) conclude on the complexity class for the algorithm by a proof.

Analyze the number of additions in terms of n. Assume that n = 2^k.

int binaryDigits(int n) { // count the number of binary digits in ns binary representation. // n is a positive decimal integer

if (n == 1) return 1;

else return binaryDigits() + 1;

}

In/2