complexity of a recursive function inside another recursive function

Question

I can't figure out the solution of this excercise:

Calculate the complexity of f(g(n))+g(f(n)) with g and f defined as follows:

int f(int x) {
 if (x<=1) return 2;
 int a = g(x) + 2*f(x/2);
 return 1+ x + 2*a;
}

int g(int x) {
int b=0;
 if (x<=1) return 5;
     for (int i=1, i<=x*x;i++)
         b+=i;
 return b + g(x-1);
}

could anyone explain me how to get to the solution?

Answer 1

There are two separate steps to solving this problem. Firstly we must look at the time complexity of each function, and then the output complexity.

---

Time complexity

Since g is self-contained, let's look at it first.

The work done in g consists of:

• x^2 executions of a loop
• A recursive call with parameter x - 1

Hence one might write the time complexity recurrence relation as (using upper-case to distinguish it from the original function)

To solve it, repeatedly self-substitute to give a summation. This is the sum of the squares of natural numbers from 6 to x:

Where in the last step we used a standard result. And thus, since a is a constant:

Next, f:

• One call to g(x)
• One recursive call with parameter x / 2
• Some constant amount of work

Using a similar method:

Applying the stopping condition:

Thus:

Since the exponential term 2^(-x^3) vanishes:

---

Output complexity

This is basically the same process as above, with slightly different recursion relations. I'll skip the details and just state the results (using lower case for output functions):

---

Thus the final time complexity of f(g(n)) + g(f(n)) is:

Which matches the result given by your source.