Dynamization

Dynamization is a term used in computer science for the process of transforming a static data structure into a dynamic one. Although, static data structures may provide very good functionality and fast query, there are not very useful because of their inability to grow/shrink. Dynamization techniques exist to make the transformation, without introducing a huge overhead amount.

Decomposition

Decomposition is a term used in computer science to break static data structures into smaller units of unequal size. The basic principle is the idea that any decimal number can be translated into a representation in any other base. For more details about the topic see Decomposition (computer science). For simplicity, binary system will be used in this article but any other base (as well as other possibilities such as Fibonacci numbers) can also be utilized.

If using the binary system, a set of $n$ elements is broken down into subsets of sizes with

$2^{i}*n_{i}$

elements where $n_{i}$ is the $i$-th bit of $n$ in binary. This means that if $n$ has $i$-th bit equal to 0, the corresponding set does not contain any elements. Each of the subset has the same property as the original static data structure. Operations performed on the new dynamic data structure may involve traversing $\log _{2}\left(n\right)$ sets formed by decomposition. As a result, this will add $O(\log \left(n\right))$ factor as opposed to the static data structure operations but will allow Insert/Delete operation to be added.

Kurt Mehlhorn proved several equations for time complexity of operations on data structures dynamized according to this idea. Some of these equalities are listed.

If

$P_{S}\left(n\right)\,\!$ = time to build the static data structure
$Q_{S}\left(n\right)\,\!$ = time to query the static data structure
$Q_{D}\left(n\right)\,\!$ = time to query the dynamic data structure formed by decomposition
${\overline {I}}$ = amortized insertion time

Then

 $Q_{D}\left(n\right)=O(Q_{S}\left(n\right)\log \left(n\right))\,\!$
 ${\overline {I}}=O(P_{S}\left(n\right)/n\log \left(n\right))$

If $Q_{S}\left(n\right)$ is at least polynomial, then $Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)$.

Static data structure

Some data structures are, by nature, static. They offer good time and space complexities for answering queries, but do not implement methods by which to change the data, once the structure is formed. There are examples of static data structures in computational geometry. One such example is a voronoi diagram.

Static data structures can be made dynamic, sometimes at no extra cost.

Further reading

Kurt Mehlhorn, Data structures and algorithms 3, . An EATCS Series, vol. 3, Springer, 1984.