What is the algorithmic time complexity of this program?

Question

I wrote a simple program in java to create and maintain Dynamic Arrays:

public class DynamicArrays {
    private Integer[] input = new Integer[1];
    private Integer length = 0;
    private Integer capacity = 1;

    /**
    * Big O Analysis of add:
    * 1+1+addBulk
    * 2+O(n)
    * So it seems add is an O(n) operation!
    * But add is only called when capacity is full and how many times can that happen?
    * Let's say there are 8 elements added.
    * so capacity will become full after 1st, 2nd, 4th additions. so its is Log(n) times?
    */
    public void add(Integer i) {
        input[length] = i;
        length++;
        if(capacity <= length)
            addBulk();
    }

    /**
    * Big O: O(n)
    */
    public void addBulk() {
        Integer[] newInput = new Integer[2*capacity];
        for(int i=0;i<input.length;i++)
            newInput[i] = input[i];
        input = newInput;
        capacity = capacity*2;
    }
}

Now I wonder what is the time complexity of the add operation? If addBulk() is not called, it is O(1). Else it is O(n) because addBulk() copies all the elements. However addBulk is called log(n) times of the total input.

So is the complexity O(n*log(n)) ?

I also read somewhere that the amortized complexity of dynamic arrays addition is O(2*n), hence O(n). I couldn't relate to that point from the code.

Can you please clarify?

Answer 1

The n log(n) calculation is a lower bound. It is correct in this case, but not tight - that is, it will really be O(n log(n), due to the reasoning you stated, but it will not be Theta( n log(n)).

see here why it is Theta(n).

Answer 2

It is amortised O (1) per insertion. Let's say n = 2^20. If you add 2^20 values, you call addBulk () 20 times, and it copies 1, 2, 4, 8, 16, ..., 2^18, 2^19 values. The sum is 2^20 = n. So n insertions take O (n), a single insertion is amortised constant time or O (1).

"Amortised" means that any single operation could take much longer than the suggested value, but that single operation does work that further operations will use, so when you do many operations, it will average out to the amortised time.