online.0227 - 8 months ago 65

Java Question

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

Here is Question:

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.)}

Source (Stackoverflow)