Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:
Contents
Problems of this class have the following measures of complexity:
The overall set of computations for a dynamic problem is called a dynamic algorithm.
Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions.
Special cases
Incremental algorithms, or Online algorithms, are algorithms in which only additions of elements are allowed, possibly starting from the empty/trivial input data.
Decremental algorithms are algorithms in which only deletions of elements are allowed, starting with an initialization of a full data structure.
If both additions and deletions are allowed, the algorithm is sometimes called fully dynamic.
Maximal element
The problem may be solved in O(N) time.
A well-known solution for this problem is using a self-balancing binary search tree. It takes space O(N), may be initially constructed in time O(N log N) and provides insertion, deletion and query times in O(log N).
Graphs
Given a graph, maintain its parameters, such as connectivity, maximal degree, shortest paths etc., when insertion and deletion of its edges are allowed.