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$
5
  • $\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, 2020 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$ Mar 8, 2020 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, 2020 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$ Mar 9, 2020 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, 2020 at 6:26

4 Answers 4

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.

$\endgroup$
2
  • $\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$ Mar 8, 2020 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, 2020 at 19:34
0
$\begingroup$

You are facing a special type of analysis, called amortized. This is necessary when the running time of an operation can vary widely from one execution to the next, for instance due to periodic reorganization.

The main purpose of the study is to establish an $O(n)$ bound ("at most") for the insertion of $n$ elements (because we are always interested in the worst-case behavior of algorithms). But in this case, $O(k)$ is not required on every $k^{\text{th}}$ insertion, only when the capacity is exceeded, and a doubling performed.

This is why the author observes that it takes $\Omega(n)$ insertions ("at least") before the capactiy is exhausted, so that in the end, the average cost of an insertion is $O(1)$.


In the usual algorithm complexity analysis, usually only $O$ estimates are needed. And conversely, when studying the complexity of a problem, $\Omega$ bounds are established, as being impassable barriers. For instance, bubble sort sorts in $O(n^2)$ operations, and it is known that a comparison-based sort takes at least $\Omega(n\log n)$ operations.

$\endgroup$
0
$\begingroup$

O(f(n)) could be a lot smaller than f(n). An extreme one: n = O(n!).

When you divide by some amount and that amount is O(f(n)) then the actual amount could be much less than f(n) which would make the result arbitrarily large. So dividing by some amount, you want a lower bound, not an upper bound.

$\endgroup$
0
$\begingroup$

No one seems to be addressing your actual question, though @vonbrand comes close. Importantly, you need to understand that statements using big-O notation (and the related notations) are not statements about algorithms but actually statements about functions. In the context of algorithm analysis, we often want to say something about the function $T: \mathbb{N} \to \mathbb{N}$ where $T(n)$ is the maximum number of "elementary operations" performed by an algorithm on any input of "size" $n$ (usually measured in bits). We often shorten our language and say stuff like "this algorithm runs in time $O(f(n))$.

In this particular example, the authors are analyzing a function that, when given $N \in \mathbb{N}$ returns the number of elementary operations performed when $N$ insertion/deletion operations are performed on a dynamic array. The idea of this analysis is that we can consider the total number of operations performed by our algorithm as the sum of the operations performed by the algorithm to make each individual insertion/deletion. Most of these will take a constant number, ie $O(1)$, of operations, but whenever an insertion/deletion causes us to resize the array, it takes more time.

The authors then note that after any resizing of the array (or initializing the array), if the array has $m$ elements, and size $d$, it will be the case that $d \approx 2m$. When the next resizing happens, the number of elementary operations needed will be a function of $d$ but since $d \approx 2m$ we can say it is a function of $m$ as well. This function will be in the class $O(m)$. Now, consider the number of insertions/deletions needed before another resizing occurs, as a function of $m$. This function will be in the class $\Omega(m)$. This means that the number of operations needed to resize the array grows like a constant multiple of the number of insertions/deletions made since the last resizing. So the total number of operations spent resizing the array throughout all of our $N$ insertions/deletions is bounded by a constant multiple of the number of insertions/deletions we performed, that is, by $N$.

$\endgroup$

Your Answer

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

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