Question

Show the analytical time complexity. Show all work.

public static void foo(int n, char A, char B, char C) {

      if (n<=0) return;   // primitive operation

      foo(n-2, A, C, B);

      for (int i=0; i<n; i++) System.out.println(“n=” + n); // primitive operation

      foo(n-2, B, A, C);

}

Answer 1

there are two recursive calls of size n-2
and work done in each recursive call is O(n)

recurrence relation:
---------------------
T(n) = 2T(n-2) + O(n)

solving the recurrence relation:
---------------------------------
T(n)
= 2T(n-2) + O(n)
= 2(2T(n-4) + O(n-2)) + O(n)
= 2(2T(n-4) + O(n)) + O(n)  (because O(n-2) is O(n))
= 2(2(2T(n-6) + O(n)) + O(n)) + O(n)
= 2^3 T(n-6) + 2^2(O(n)) + 2^1(O(n)) + 2^0(O(n))
= (2^(n/2) + ... + 2^2 + 2^1 + 2^0) * O(n)
= (2^(n/2) (1 + 1/2 + 1/4 + ...)) * O(n)
<= 2^(n/2) * 2 * O(n)

so, T(n) is O(n * 2n/2)