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?
