Question

static int F(int n) {

if (n < 1)

return 1;

else

return 2*F(n-1)+n;

}

(a) [7 points] Give the recurrence that describes the running time of F(int n).

(b) [8 points] Solve the recurrence equation from (a).

Note: For (b), you must show your work

Answer 1

a) Let the function T(n) denote the number of elementary operations performed by the function call F(int n).

We identify two properties of T(n).

• Since n<1 is computed using a fixed number of operations k₁, T(1) = k₁ (here n<1 value =1 base case)
• If n > 1 the function will perform a fixed number of operations k₂, and in addition, it will make a recursive call to F(n-1). This recursive call will perform T(n-1) operations. In total, we get T(n) = 2F(n-1)+n

b) Just looking at the recurrence we can guess that T(n) is something like 2^n. we can verify that with first few values of T(n), we discover that they are each n less than a power of two.

It looks like T(n) = 2 ⁿ − n might be the right answer. Let’s check.

T(0) = 1 = 2⁰− 0

ie T=1 so it satisfies

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

= 2(2 ⁿ⁻¹ − n) + n [induction hypothesis]

= 2 ⁿ − n [algebra]

hence solved