Сложность времени цикла, содержащего рекурсивную функцию

Question

У меня возникли сложности с обработкой временной сложности следующего кода:

int f(int n)  {

int x=1;
for (int k=0; k<n; k++){
x *=n*n
} 
g(n);
return x; }

Где g (n) - рекурсивная функция:

void g(int n){
   if (n<1)
     return;
g(n/2);
}

Спасибо!

Answer 1

int f(int n)  {
int x=1;
// O(n) time complexity due to for loop
for (int k=0; k < n; k++) { 
  // O(1) 
  x *= n*n 
} 
// O(log n)(base 2) because for every time we divide by 2 before calling the function 
g(n); 
return x;
}
void g(int n){
 if (n<1)
  return;
 g(n/2);
}

Теперь O (logn) быстрее, чем O (n), что означает, что общая временная сложность кода просто O (n) !!

Answer 2

Сложность g(n) равна O(log n).

Сложность f(n) равна O(n + log n) (n для цикла for, log n для вызова g(n)) - или просто O(n), как указано Шипрой Гуптой.

int f(int n)  {
  int x=1;
  for (int k=0; k < n; k++) { // O(n)
    x *= n*n // O(1)
  } 
  g(n); // O(log n)
  return x;
}

O(n * 1 + log(n) + 1)

То есть, если мы игнорируем тот факт, что g(n) никогда не достигнет условия n<1, если n >= 1 (переполнение стека!) ... говоря о котором - добро пожаловать на сайт! : -Р