Running Time

Calculate the time T(N) that each of the following recursive functions takes to execute. That is, find the recursive function T(N), for example: T(N) = 3* T(N/2). You do not need to solve the recursive equation.

int foo(int N) {
  if (N == 0)
    return 1;
  else 
    return N * foo(N-1);
}


int bar(int N) {
  if (N == 1)
    return 1;
  for (int i = 1; i < N; i++){
    bar(N-1);
  }
}

int bazo(int N) {
  if (N < 1)
    return 1;
  for (int i = 1; i < N*N; i++){
    for (j = 1; j < i; j++) {
      bazo(N/2);
    }
  }
}

int hard(int N) {
  if (N < 1)
    return 1;
  return (N*hard(N/2))/hard(N-1);
}

Any computer science student shoud be able to calculate hat:

foo(N) = T(N) = T(N-1) = T(N)
bar(N) = T(N) = (N-1)*T(N-1)
bazo(N) = T(N) = N2*O(N2)*T(N/2)
hard(N) = T(N) = T(N/2)+T(N-1)