-1
$\begingroup$

Me again.

This time I have a more general question.

Suppose I have the following code snippet:

int f(int k) {
  int s=0;
  for(int i=0; i<k*k; i++) {
   s++;
}
 return 2*k*k;
}

And the expression is:

f(n) * f(f(f(n)));

I am told that the complexity is O(n^2) + O(n^2) + O(n^4) + O(n^8)

I have several questions:

  1. Why is there a plus sign when the function calls itself. Shouldn't it be "*" in between the last three terms?

  2. What if the expression was f(n) + f(f(f(n)));, would it still be the same?

And lastly and most importantly,

  1. What if it was this expression?

f(n) + f(z)*f(f(n))

This also confuses me very much. Most notably because there is a new variable z, and also because I am not sure that even if it was f(n) instead of f(z), should I multiply the complexity with f(f(n)) or add it to it.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
0
$\begingroup$

f(k) performs k^2 operations. f(n) returns 2n^2, f(f(n)) returns 8n^4, so you calculate f(n) * f(8n^4). This takes about 64n^8 operations and the result is 2n^2 * 128n^8 = 256 n^10.

There are O(n^4) other operations which we can ignore because that number is much smaller than 64n^8. The time complexity is O(n^8) or more precise $\theta(n^8)$.

However, any decent compiler will realise that all the additions are not needed and give the result in O(1).

In your second example, you calculate f(z) with z^2 operations, f(f(n)) with 4 n^4 operations, then multiply which is ONE operation. The product takes z^2 + 4m^4 + 1 operations.

Improve this answer
$\endgroup$
0
$\begingroup$

Consider the following equivalent way of computing the expression:

x_1 = f(n);
x_2 = f(x_1);
x_3 = f(x_2);
return x_1 * x_3;

What are the (approximate) magnitudes of the different variables? What is the complexity of each call to f? What is the complexity of the multiplication on the last line? Then put this all together.

Improve this answer
$\endgroup$
5
  • $\begingroup$ is this for my first or second expression? $\endgroup$ Commented Nov 22, 2023 at 19:59
  • $\begingroup$ @johndoe For your first expression. If you want it for your second expression, replace the multiplication with an addition. $\endgroup$ Commented Nov 22, 2023 at 20:00
  • $\begingroup$ The complexity of each call to function f is O(n^2), and the complexity of the last line is constant O(1). How could I set up my second example in the same way? the f(n) + f(z)*f(f(n))? This confuses me a bit since I have a function call that multiplies another function call (which calls the same function), to which you add another function call. $\endgroup$ Commented Nov 22, 2023 at 20:03
  • $\begingroup$ Are you sure the call f(x_1) happens in $O(n^2)$ time? It happens in $O(x\_1^2)$ time, but remember that x_1 is $\Theta(n^2)$ already, so $O(x\_1^2)$ is actually $O(n^4)$. For the expression with z inside of it, it is impossible to get an asymptotic expression containing only n without knowing how big z is compared to n. $\endgroup$ Commented Nov 22, 2023 at 20:52
  • $\begingroup$ oh absolutely, sorry. I was saying that a function call has the time complexity of its squared argument. It would be different for f(f(n)) in that it would be O(n^4). Ah, okay I understand. What if instead of f(z) I had f(n) + f(n)*f(f(n))? $\endgroup$ Commented Nov 22, 2023 at 22:21
0
$\begingroup$

A single call of f with the argument n has complexity n².

The first call is made with the argument n, and costs O(n²).

Then for the nested calls, the innermost call is made with the argument n, and costs O(n²).

The intermediate call is made with the argument 2n², and costs additional O((2n²)²).

The outermost call is made with the argument 2(2n²)², and costs additional O((2(2n²)²)²).

In total, it is enough to write O(n^8).

The costs do not multiply because only one call is involved every time (there are no recursive calls in the loop).

2.

The number of operations is the same.

3.

O(z^2+n^4).

Again, there is no reason to multiply.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.