7. (10%) Consider the following function implemented in C. Please analysis the time complexity of bar(N, 'A', 'B', 'C') in Big O notation using substitution method for solving recurrence relation. Please clearly show the steps of your analysis.

void bar(int N, char X, char Y, char Z)
{
  if (N<=1)
    printf("%c %c\n", X, Y);
  else  {
    foo(N-1, X, Z, Y);
    printf("%c %c\n", X, Y);
    foo(N-1, Z, Y, X);
  }
}