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

| cite | improve this answer | |
$\endgroup$
  • $\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 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 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

| cite | improve this answer | |
$\endgroup$
  • 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 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 at 22:27

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

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