1

Click here to check question image

Hello, I have 2 functions in the image. And the question is about getting their runtime.

The answer for EX4 function is O(n^2) and EX5 is O(n^4). I don't get this.

Question for EX4:

we have inner loop that starts with j=0 to i. From my perspective, this is equivalent to "1+2+...+n", so is "n(n+1)/2", therefore, O(n^2) for inner loop only. However, we also know that outer loop runs from i=0 to n, which is O(n). So the answer I thought for EX4 was actually "O(n) * O(n^2) = O(n^3)". But the real answer says O(n^2). Why is that?

Question for EX5:

Similarly, I thought it is "n*(n+1)/2 = O(n^2)" for inner loop and also "n*n=O(n^2)" for outer loop, so the whole runtime become O(n^2) * O(n^2) = O(n^4), which is same as real answer of this question. But if I justify this in this way, then my solution to EX4 doesn't make sense. Why is it O(n^4) specifically?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Ryu
  • 27
  • 2
  • Ex5(n) = Ex4(n^2). So if you can calculate the runtime of Ex4 as a function of its input, say f(n), then you immediately have the runtime of Ex5, namely f(n^2). – Paul Hankin Jun 14 '17 at 18:32
  • 1
    Ex 4: "1+2+...+n" is the number of times the inner loop executes **in total**, why would you multiply that by `n` at the end? – Bernhard Barker Jun 14 '17 at 18:32
  • Ex 5: The inner loop executes `1+2+...+x = x(x+1)/2` times, where x is n^2, which directly leads you to O(n^4) (also with no multiplication like you did in ex 4). – Bernhard Barker Jun 14 '17 at 18:34

0 Answers0