CODEWITHSUNDEEP
c++time-complexitybig-oasymptotic-complexity
DataJayden
DataJayden

Reputation: 73

Time complexity of function calling another function?

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()?

Upvotes: 7

Views: 12743

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

This is intuitively n²log(n), but more precisely, you get the following proof:

enter image description here

enter image description here

Upvotes: 1

galinette
galinette

Reputation: 9292

In order to find the complexity of f, just inline the code of g inside f, and think as if this was a single whole function. The call himself is O(1) and thus has no impact on complexity, it's as if the code inside g was executed at the place where g is called.

This would be untrue in some cases, for instance if you pass by value an array of size n as a parameter to the function : in this case, the array copy itself would be O(n), so the call would have some effect on complexity.

Upvotes: 1

Reazul Hasan Russel
Reazul Hasan Russel

Reputation: 164

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(n2) & g's complexity is O(lg(n)), yielding an overall complexity of O(n2lg(n))

Upvotes: 5

Jarod42
Jarod42

Reputation: 217980

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)).

Upvotes: 2

Related Questions