Time complexity of function calling another function?

Question

I know how to find the time complexity for almost any option (simple function, function with loops, etc.), but I can't figure out how to determine time complexity of function that is calling another function, specifically if the calling function is inside a loop.

I wrote some functions, that I use as example.

int g(int k) {
  int i=0;

  while(k>0) {
    i += k;
    k= k/2;
  }

  return i;
}

int f(int n) {
  int m = 0;

  for (int i=0; i<n; ++i) {
    for (int j=i; j<n; ++j) {
      m += g(j);
    }
  }

  return m;
}

I can't figure out: do I have to consider the time complexity of function g(), and if I have to how to calculate it in function f()? Or do I just ignore function g() and include just the function calls in function f()?

Answer 1

As, the function g's complexity depends on the parameter k (logarithmic), you have to consider it while calling it from function f. In case, if g's worst case operation has constant time complexity, then you may not need to consider it explicitly.

In your case, f's complexity is O(n²) & g's complexity is O(lg(n)), yielding an overall complexity of O(n²lg(n))

Answer 2

You have to take account complexity of g in f.

g has O(log(n)) complexity.

so complexity of f is the sum of those complexity log(j)s.

At worst it is O(n²log(n)).