Array Doubling
* 우리는 계산할때 배열이 얼마나 필요한지 모른다.
* 새로운 원소를 삽입할때 room 이 필요하다면
- 두배의 길이 배열을할당한다.
- 새로운 배열로 값을 옮긴다
* t를 배열을 옮기는데 사용되는 cost 라고 하자.
- (n+1)을 삽입할때 doubling 이 발생한다고 하자.
-t*n의 시간이 걸린다 array-doubling 에
- t*n/2 + t*n/4 + t*n/8 + ... for previous array doubling
- 이것들은 t*n 보다 작다.
- total cost < 2t*n