0
$\begingroup$

My algorithms and data structures' book states that to create a dynamic array the following procedure is followed:

Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in it. Each time an insertion operation is done, if there is enough space $(n+1<d)$, $n $grows by 1; otherwise if $n=d$, we allocate and array $b$ of size $2d$, $d$ is updated to$ 2d$ and all elements are copied to it, then we do $a=b$. Similarly, everey time a deletion operation is performed, $n$ decreases by 1, when $n=d/4$, we allocate and array of size $d/2$, $d$ is updated to $d/2$ and we copy all elements of the array $a$ to the array $b$ an do $a=b$.

The pseudocode of the functions doing the array doubling and halving is shown in the picture

enter image description here

then the following theorem is proved:

The execution of N insertion or deletion operations in a dynamic array requires a time $O(n)$, beside d=$O(n)$

proof: Let $d$ be the length of an array and n the number of elements stored in it After doubling the array's size there are $m=d+1$ elements in the new array of $ 2d $ positions. We need at least m-1 insertion requests for a new doubling and at least $m/2 $ deletion requests for a halving. Similarly,after a halving, there are$ m=d/4$ elements in the new array of $ d/2 $ elements, for wich at least$ m+1$ insertion requests are needed for a new doubling and at least $m/2 $ deletion requests are needed for a new halving.

In any case, the cost of $ O(m) $time required for the resizing can be virtually distributed among the $ \Omega(m)$ operations that caused it(starting from the last resizing) . Finally, supposing the when the array is created there are $n=1$ and $d=1$, the number of elements of the array is always one fourth of its size, so $d=O(n)$

I am a beginner with this $ \Omega(m)$ and $ O(m)$ , I know the mathematical definitions and I've been reading a lot about it but I am not able to understand it well in context. I know big O should indicate an upper bound on the time complexity of an algorithm and big omega a lower bound.

I don't understand the last paragraph when they use these symbols, Why is the time cost O(m), why are they using $ \Omega(m)$ for the number of operations that caused the resizing (besides specifically what operations are they referring to?) and why do they write $d=O(n)$, what should I understand from it? Any help will be greatly appreciated

Note: I got this from : Strutture di dati e algoritmi, progettazione, analisi e visualizzazione. Crescenzi, Gambosi, Grossi-2nd edition.

$\endgroup$
  • $\begingroup$ It's a hand-waving amortization argument: they say, we have cost $O(m)$ across $\Omega(m)$ operations, so we can virtually assign each operation cost "$O(m) / \Omega(m)" "=" $O(1)$. Search for "amortized analysis" to find more elaborate examples. $\endgroup$ – Raphael Mar 8 at 21:09
  • $\begingroup$ @ Raphael, thanks for answering, why do they use $\Omega(m)$ for the number of operations and not $O(m)$ or $\Theta(m)$? Same for the cost why $O(m)$ and notany other symbol? $\endgroup$ – J.C.VegaO Mar 8 at 23:23
  • $\begingroup$ Think about what this "division" gives you when you don't have an upper bound in the nominator and a lower bound in the denominator. You can ignore Landau notation for this. $\endgroup$ – Raphael Mar 8 at 23:47
  • $\begingroup$ I understand it gives the mean cost per operation, what I like to understand is actually why have they chosen these particular bounds(symbols). It doesn't seem to change anything if I use any of the other 2 symbols $\endgroup$ – J.C.VegaO Mar 9 at 0:15
  • $\begingroup$ Amortized, not mean. Be aware of the difference. As for Landau symbols: $\Theta$ would work, of course, at it implies both $O$ and $\Omega$; it creates more burden of proof, though. It definitely changes something if you use $\Omega$ in place of $O$ and vice versa. Plug in some (non-tight) functions allowed in either case and see what happens. $\endgroup$ – Raphael Mar 9 at 6:26
0
$\begingroup$

The definitions are (as used commonly in Computer Science, all functions positive):

$f(n) = O(g(n))$ if there is $c_1 > 0$ such that for some $N_1$ whenever $n \ge N_1$ it is $f(n) \le c_1 g(n)$

$f(n) = \Omega(g(n))$ if there is $c_2 > 0$ such that for some $N_2$ whenever $n \ge N_2$ it is $f(n) \ge c_2 g(n)$

$f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

Note that the values of $N_i$ might be huge, and nothing is said about the values of $c_i$. This is a rather crude comparisons for very large $n$. Useful because they are (comparatively) easy to get, and we are mostly interested in our algorithm's performance for large inputs (small ones are dispatched with not too much work).

Informally, $f(n) = O(g(n))$ means $g$ is an upper bound to $f$, $f(n) = \Omega(g(n))$ means $g$ is a lower bound, $f(n) = \Theta(g(n))$ that they grow roughly at the same rate. Note that for example $n = O(n^3)$ and $n = \Omega(\ln n)$. The notation does not mean $g(n)$ is "best possible" in any sense. Often it is understood from the context that the bounds are tight, but you have to check the context/derivation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you explain why in the last paragraph of the proof they say that the time cost is $O(m)$ and the number of operations $\Omega(m)$. I don't get why the write that. $\endgroup$ – J.C.VegaO Mar 8 at 1:32
  • $\begingroup$ @juancarlosvegaoliver, you can use the above on any function you like. If $m$ is (some measure of) the size of the input, you can e.g. consider the time to do the job, or the number of certain operations, or what have you. Why they are interested in those particular values here, I can't say. $\endgroup$ – vonbrand Mar 8 at 19:34

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.