0

Consider an Arraylist. Internally it is not full, and the number of elements inserted so far is known. The elements are not sorted. Choose the operations listed below that are fast regardless of the number of elements contained in the ArrayList. (In other words, takes only several instructions to implement).

Insertion

Insertion at a given index

Getting the data from a specified index

Finding the maximum value in an array of integers (not necessarily sorted)

Deletion at the given index

Replacing an element at a specified index

Searching for a specific element

I chose Insertion at specified index, Getting the data from a specified index, and replacing an element but answer key says Insertion. As I usually understand it, in an ArrayList, the insert operation requires all of the elements to shift left. If we did this at the beginning of the list, we would have $O(n)$ time complexity. However, if we did it at the end, it would be $O(1)$.

My question comes down to: (1) what, if any, difference is there between insertion and insertion at specified index and (2) given this particular time complexity for insertion why is it considered "fast"

user278039
  • 139
  • 6
  • The answer key is giving an option that isn't on the list of alternatives. Note that when it comes to Java's `ArrayList`, insertion without specifying an index inserts at the end (i.e., appends). – Ted Hopp Mar 24 '17 at 06:24
  • @TedHopp My bad, there are two distinct answer choices. One is insertion and another is insertion at specified index – user278039 Mar 24 '17 at 06:28

4 Answers4

0

For the first question the answer is this:

  • Insertion at a specified index i takes O(n), since all the elements following i will have to be shifted to right with one position.
  • On the other hand, simple insertion as implemented in Java (ArrayList.add()) will only take O(1) because the element is appended to the end of the array, so no shift is required.

For the second question, it is obvious why simple insertion is fast: no extra operation is needed, so time is constant.

aUserHimself
  • 1,589
  • 2
  • 17
  • 26
0

(1) what, if any, difference is there between insertion and insertion at specified index and

An ArrayList stores it's elements consecutively. Adding to the end of the ArrayList does not require the ArrayList to be altered in any way except for adding the new element to the end of itself. Thus, this operation is O(1), taking constant time which is favorable when wanting to perform an action repetitively in a data structure.

Adding an element to an index, however, requires the ArrayList to make room for the element in some way. How is that done? Every element following the inserted element will have to be moved one step to make room for the new insertion. Your index is anything in between the first element and and the nth element (inclusively). This operation thus is O(1) at best and O(n) at worst where n is the size of the array. For large lists, O(n) takes significantly longer time than O(1).

(2) given this particular time complexity for insertion why is it considered "fast"

It is considered fast because it is O(1), or constant time. If the time complexity is truly only one operation, it is as fast as it can possibly be, other small constants are also regarded fast and are often equally notated by O(1), where the "1" does not mean one single operation strictly, but that the amount of operations does not depend on the size of something else, in your example it would be the size of the ArrayList. However, constant time complexity can involve large constants as well, but in general is regarded as the fastest as possible time complexity. To put this into context, an O(1) operations takes roughly 1 * k operations in an ArrayList with 1000 elements, while a O(n) operation takes roughly 1000 * k operations, where k is some constant.

Big-O notation is used as a metric to measure how many operations an action or a whole programs will execute when they are run.

For more information about big O-notation: What is a plain English explanation of "Big O" notation?

Community
  • 1
  • 1
Woopdidoo
  • 21
  • 5
0

First take a look at these two methods defined in java.util.ArrayList

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
  1. Now if you see the first method (just adding element), it just ensures whether there's sufficient capacity and appends element to the last of the list.
    So if there's sufficient capacity, then this operation would require O(1) time complexity, otherwise it would require shifting of all elements and ultimately time complexity increases to O(n).
  2. In the second method, when you specify index, all the elements after that index would be shifted and this would definitely take more time then former.
Raman Sahasi
  • 30,180
  • 9
  • 58
  • 71
0

ArrayList internally is nothing but an Array itself which uses Array.copyOf to create a new Array with increased size,upon add,but with original content intact. So about insertion, whether you do a simple add (which will add the data at the end of the array) or on ,say, first(0th) index , it will still be faster then most data structures , keeping in mind the simplicity of the Data Structures.

The only difference is that simple add require no traversal but adding at index require shifting of elements to the left, similarly for delete. That uses System.arrayCopy to copy one array to another with alteration in index and the data.

So ,yeah simple insertion is faster then indexed insertion.

Adarsh Singh
  • 9
  • 5