Big Oh notation for this specific cost function

Question

Question: what is the big oh notation for the cost of a stack (that implements an array) that doubles the size of its array if it needs more space. it dynamically resizes larger, but not smaller.

ex:

N = [size]
1 = [x]
2 = [x,x]
3 = [x,x,x,x]
4 = [x,x,x,x]
5 = [x,x,x,x,x,x,x,x]
6 = [x,x,x,x,x,x,x,x]
7 = [x,x,x,x,x,x,x,x]
8 = [x,x,x,x,x,x,x,x]
9 = [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]
10 =[x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]

I got it as:

T(N) = Summation from i = 0, to log_2(N) of (2^i)

which is equivalent to (2^(log_2(n))) + 1

which I interpret as O(2^N), because lim as n -> infinity of log_2(n) = infinity.

So in essence ... what is Big Oh for this: (2^(log_2(n))) + 1

Answer 1

I am having a hard time figuring out your analysis of the code. Rather, you can convince yourself that the running time will indeed be O(N) by the following analysis:

For storing N elements, you will resize the array after the 2nd, 4th, 8th, 16th, 32nd, 64th, .....2^x element, where 2^x = N.

Thus, x = log_2 N

At each resize operation a cost equal to the size of the array is incurred. Thus the total resizing overhead can be expressed as:

cost = 2^0 + 2^1 + 2^2 + 2^3 ......2^x
     = (2^x-1)/(2-1)    
     = 2^x - 1 
     = 2^(log_2 N) - 1 
     = N^(log_2 2)-1 
     = N-1 
     = O(N)