online.0227 - 1 year ago 123
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:

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!

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

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download