1
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Hugh
    Jun 12, 2020 at 19:57
  • 2
    $\begingroup$ @Hugues Yes. Base on the definition of the asymptotic notations, the proof is straightforward. There is no extra point there. $\endgroup$
    – OmG
    Jun 12, 2020 at 22:13
0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ariel
    Jun 12, 2020 at 21:58
  • $\begingroup$ @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). $\endgroup$
    – Hugh
    Jun 12, 2020 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.