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?
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 loopx - 1Hence 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:
g(x)x / 2
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.
x.
gcan simply be computed...2 * f(x/2)instead off(x/2)+f(x/2).