CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
user1874239
user1874239

Reputation: 325

Complexity and Big-O Notation

What is the worst case time complexity for the following two algorithms assuming items (an ArrayList<Integer>)has enough unused space that it never needs to be re-sized? My initial guess is that A would run slower because it has to shift every element over to add the new one at index [0]. I think B is O(N^2) in the worst case but I am not sure.

A.

for (int i = 0; i < N; i++)
    items.add(0, new Integer(i));

and B.

for (int i = 0; i < N; i++)
    items.add(new Integer(i));

Upvotes: 0

Views: 231

Answers (3)

Varun Vats
Varun Vats

Reputation: 509

Implementation A could be, by assuming that the items array is sufficiently large, implemented as:

for (int i = 0; i < n; i++) {
    for (int j = items.size; j > 0; j++) {
        items[j] = items[j-1]; 
    }
    items[0] = i;
}

The total number of operations executed in this case (assuming m was the initial size of the items list) would be:

This has the complexity O(n2)

Option B, on the other hand, can be implemented as

for (int i = 0; i < n; i++) {
    items[items.size] = i;
    items.size++;
}

and the number of operations executed in this case will be

This has the complexity O(n)

Upvotes: 1

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

If your question is about java, then first version is slower and has complexity O(N^2)for the very reason you mention, while B has complexity O(N).

Upvotes: 1

ncmathsadist
ncmathsadist

Reputation: 4891

in A, you must shift all of the items to the right one in the internal array of the array list for each insertion. This will be O(n^2) to complete the operation. In the second case, no shifting is needed so it will be O(n). In A, you are doing tons of unnecessary and expensive work.

I am assuming, as you had stipulated, that the internal array is not resized.

Upvotes: 0

Related Questions