online.0227 online.0227 - 1 month ago 24
Java Question

How to get asymptotic running time?

I do not know how to get exact Asymptotic Complexity as following question asks me to solve.

Here is Question:

enter image description here

Everything I learned from class is that, if there exists "for loop" that runs N times, or recursively call "recursive method" N times, then either one is O(N). This is practically all the base knowledge I know of.

Question 1) What answer says about "N(N+1)/2", is this same as "O(N(N+1)/2)"?

Also, the answer says followng "On iteration i, both add and trimToSize require that i array elements be copied to a new array.", I think it says this because it calls both "list.add()" and "list.trimToSize()" N times.

From my perspective, this looks more like just O(N)... because since it adds ith element N times using "list.add()" and also array-copies element N times through "list.trimToSize()". Thus, N + N <= 2N so O(N) where witness C=2 and k=1, not O(N(N+1)/2). However, my answer is wrong. Therefore,

Question 2) I just do not know how to obtain N(N+1)/2 as answer says.

Thank you very much if you can answer!

Answer

From my perspective, this looks more like just O(N)... because since it adds ith element N times using "list.add()" and also array-copies element N times through "list.trimToSize()". Thus, N + N <= 2N so O(N) where witness C=2 and k=1, not O(N(N+1)/2).

However, my answer is wrong.

Yes. It is.

You are treating each call to trimToSize having a constant cost. That is not correct. If you look at what trimToSize does, you will that each call is copying all of the elements (so far) to a new array. That is NOT a constant cost

  • In the 1st call to trimToSize the array length is 1, so you copy 1 element.
  • In the 2nd call to trimToSize the array length is 2, so you copy 2 elements.
  • ...
  • In the Nth call to trimToSize the array length is N, so you copy N elements.

Add that all up and you get N(N+1)/2 for all of the trimToSize calls.


(In fact, the given answer for the question is skating over a couple of things that happen in the real implementation of ArrayList. But the bottom line answer is the same.

Also, note that O(N(N+1)/2) is the same complexity class as O(N^2). You can prove this from first principles.)