CODEWITHSUNDEEP
javabig-o
user4833678
user4833678

Reputation:

Inefficiency of the code

I have the code here:

import java.util.*;

public class AddElements {

    public static void main(String[] args) {

        ArrayList<Integer> a = new ArrayList<Integer>();
        for(int i=1; i<=5; i++){
          a.add(i);
        }
        System.out.println(a);
        // [1, 2, 3, 4, 5]

        addElementAtBeginning(a, -1, 4);
        System.out.println(a);
        // [-1, -1, -1, -1, 1, 2, 3, 4, 5]    

       addElementAtBeginning(a, -2, 7);
        System.out.println(a);
        // [-2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, 1, 2, 3, 4, 5]
    }

    public static <T> void addElementInBeginning1(ArrayList<T> a, T fillElem, int nFills){
          for(int fills=0; fills<nFills; fills++){
               a.add(fillElem);
               for(int i=a.size()-1; i>0; i--){
               a.set(i, a.get(i-1));
          }
          a.set(0, fillElem);
        }
    }

    public static <T> void addElementAtBeginning2(ArrayList<T> a, T fillElem, int nfills){
        for(int i = 0; i < nfills; i++){
            a.add(0, fillElem);
        }
    }
}

Both of the methods produce the same result. The problem is in their efficiency. I just want to make sure that the first method, addElementAtBeginning1(), takes O(N^2) and addElementAtBeginning2() takes O(N). Am I correct?

Upvotes: 1

Views: 84

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727027

This is incorrect: both your methods take O(F * (N+F)) time, where N is the number of elements in the list, and F is your nFills variable.

The reason addElementInBeginning1 takes O(F *(N+F)) is simple: it has two nested loops, one on nFills and the other one on N, with the nested loop performing O(1) operations. The size of the array list at the end of the operation is N+F.

The reason addElementInBeginning2 takes O(F *(N+F)) is dependent on the data structure used in the implementation: each iteration of the loop that executes nFills times takes time dependent on the data structure. For ArrayList the time of inserting at zero is O(N). For a linked list the time is O(1), so the overall time with a linked list would have been O(F).

Upvotes: 3

Related Questions