$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

Question

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

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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