Amortized time for dynamic array

Question

I'm struggling to understand one part from the book "Cracking the coding interview". The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full and we have to reallocate.

Inserting $X$ elements take $O(2X)$ (because $\frac{X}{1} + \frac{X}{2} + \frac{x}{4} + \ldots + 1 \approx 2 X$)

I perfectly understand until this point but I don't understand second sentence:

"Therefore, $X$ insertions take $O(2X)$ time. The amortized time for each insertion is $O(1)$."

How did she came to this conclusion?

Answer 1

You should read more precisely the definition of amortized analysis. As we have $X$ operations here, the time complexity of these operations should be divided by the number of operations to find the amortized complexity of the algorithm. Hence, $\frac{O(2X)}{X}$ is the amortized complexity of the insertion algorithm which is $O(1)$.

Answer 2

From this post on Mathematics stackexchange :

$\Theta(g)$ is set of functions $\left\lbrace f: \exists c_f,C_f>0, \ \exists N,\ n>N, c_fg \leqslant f \leqslant C_f g\right\rbrace$. We consider only non negative functions.

There are some properties outgoing from definition: $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ $$\Theta(f) + \Theta(g)=\Theta(g + f)$$ And for $g>0$ holds $\frac{\Theta(f)}{g} = \Theta \left(\frac{f}{g}\right)$

It's straightforward to demonstrate those three properties. Please let me know if you want me to add them to this answer.

Thus we can assume $\frac {O(2X)}{X} = O(\frac {2X}{X}) = O(2) = O(1)$ with $O$ <=> $\Theta$ in the context of computer science:

"In industry (and therefore in interviews), people seem to have merge $Θ$ and $𝑂$ together. Industry's meaning of big $O$ is closer to what academics mean by $\Theta$, in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is $O(n)$. "
- Cracking the Coding Interview