8

I have an array list which I iterate through. In each iteration I call get() to get one element, and if that item passes some condition, it is added to a new array list using add()

List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
    Item toCheck = items.get(i);
    if(toCheck meets some condition){
        lessItems.add(toCheck);
    }
}

I am not sure what the time complexity is here. I am calling get() on all items so that is O(n). Then I am also calling add() on potentially all the items so there's another O(n). Not too sure on this one.

Mark
  • 2,167
  • 4
  • 32
  • 64
Chicken Crimpy
  • 91
  • 1
  • 2
  • 6
  • 3
    It's O(n) + O(n) which is O(2n), and you can drop the 2 (because it is constant relative to the input) and say it is O(n). – Elliott Frisch Sep 17 '16 at 00:58
  • 1
    @ElliottFrisch that's not true. inserting at last element of arraylist in java is not `O(n)`. Please see my answer. – hqt Sep 17 '16 at 01:52
  • @ElliottFrisch apparently others disagree with you. Enough to downvote my answer, which is the same as yours. – Mike Nakis Sep 17 '16 at 09:17
  • I don't get the disagreement. Aren't all the answers saying the same thing, that's it's O(n)? O(n) to get the items, and O(n) to add the new items. – fgb Sep 17 '16 at 09:25
  • @fgb what appears to be happening is that hqt is inventing fictitious reasons due to which other answers are wrong, so as to proclaim his answer right. And it appears that he has managed to fool some voters to that effect. – Mike Nakis Sep 17 '16 at 09:32
  • @fgb no. inserting at the end of the list is O(1), not O(N). and in case O(N), complexity should be O(N^2). Not O(N*2) as others said. – hqt Sep 17 '16 at 09:41
  • @hqt No one's saying inserting at the end of a list is O(n). That's also why they're not calculating the total complexity as O(n^2). Inserting n items into a list is O(n), and reading n items from a list is O(n), as the question says. Both these are done, so the total complexity is the sum. – fgb Sep 17 '16 at 09:55
  • @fgb understood. I'm really sorry for my misunderstanding. :) – hqt Sep 17 '16 at 10:04
  • @Mike My "answer" was a comment, but correct. O(1) called n times is O(n). – Elliott Frisch Sep 17 '16 at 15:34
  • 1
    @fgb, the disagreement is the lack of clarity and accuracy. There's *one* loop that makes this `O(n)`. After that you have a number (not 2) of constant time operations. They shouldn't be saying the way @Elliott did in the previous comments. It's incorrect and inaccurate to say `O(n) + O(n)` because the second complexity exists internal to the first (IOW, it's not addition but multiplication of constant terms); it's `cn = `O(n)`. – ChiefTwoPencils Sep 18 '16 at 17:18
  • @ChiefTwoPencils That doesn't make any difference, `(c + d)n` is equal to `cn + dn`. You're reading too much into the form of the expression. It's only separated like that for convenience, and to match the complexities given in the question. – fgb Sep 18 '16 at 17:47
  • 1
    @fgb, it's true they're equivalent if you wanted to extract the getting and adding out and match what OP did. But it's still incomplete. They're obviously "Not too sure on this one" so why not be exact or at least not incomplete with `O(n) + O(n)`? There's other time left out. – ChiefTwoPencils Sep 18 '16 at 18:04

4 Answers4

10
  1. Your first loop for iterating items list: complexity is O(n)
  2. Insert each item to end of list lessItems: in normal array it will be O(n) as others said. But Java implements for ArrayList using amortized array. This means when inserting at the end of array, algorithm only costs Amortized O(1). Or you can say O(1)

So complexity of your code is: O(n) * amortized O(1). In short is O(n)

Another reference:

dynamic array

Additional note 1:

If complexity of inserting at the end of array is O(N), so the total complexity is O(N^2), not O(2*N) as other answers said. Because the total complexity for inserting would be: 1 + 2 + 3 + ...+ n = n*(n+1)/2

Addtional Note 2:

as official document states:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Additional note 3:

Here is the logic of grow method that I have taken from official java source code:

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

As the source code has said, when program add element that make size of array larger than current capacity, Array will be grown. new size of grown array will be:

int newCapacity = oldCapacity + (oldCapacity >> 1);

This is a trick that make inserting is amortized O(1)

hqt
  • 29,632
  • 51
  • 171
  • 250
2

You are doing an iteration, and that's of O(n).

You're also adding items to an ArrayList, which is of O(1) (Amortized)

Getting an index is also O(1).

So your doing O(n) times, operations of O(1), which is going to be of O(n).

SpiXel
  • 4,338
  • 1
  • 29
  • 45
1

Big-O and similar notations are asymptotic bounds on time complexity. They discard the numeric coefficient and are used to estimate run-time as a function of size of input.

So, 2*n, 3*n,etc. are represented as O(n), and 2*nlog(n), 3*nlog(n),etc. are represented as O(nlog(n)).

Since the add() operation inserts only one element in this case, its runtime is approximately, (some small constant)k*1, giving the total runtime as (some constant)j*(n+some constant(k)), in other words j*n, or O(n).

In this case and all such similar cases, any constant k multiplied by n would be represented as O(n) meaning the runtime varies linearly with size of the input ArrayList.

brijs
  • 525
  • 6
  • 18
0

For iterating through the array list, the time complexity will be O(n). n will be the size of the list.

for getting the value using get(), it will be O(1), random access is possible in array list using index.

And for adding the values using add(), the value is getting added at the last, so it will be O(1).

The time complexity of this operation will be O(n).

Vijai
  • 1
  • 3