# Amortized time for dynamic array

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?

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)$$.

• I don't think this answer is misleading. Why $\frac{𝑂(2𝑋)}{𝑋} = O(1)$? Does it come from your intuition? Please see my answer for a real mathematical proof of why is it true – Hugh Jun 12 at 19:57
• @Hugues Yes. Base on the definition of the asymptotic notations, the proof is straightforward. There is no extra point there. – OmG Jun 12 at 22:13

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

• I have no idea what $O\iff \Theta$ means. $f=O(g)$ is definitely not equivalent to $f=\Theta(g)$. The only meaning I can attribute to this statement is that for practical applications you are usually interested in upper bounds on the complexity, and lower bounds or tight bounds (reflected by $\Theta$) are usually more theory oriented. Still, this is a very bad sentence. – Ariel Jun 12 at 21:58
• @Ariel Sorry if it's unclear. From the book I was refering to: "In industry (and therefore in interviews), people seem to have merge $\Theta$ and $O$ 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). – Hugh Jun 12 at 22:27