Resources

• Sum of Harmonic Series is O(log n)

• LIS with Segment Tree

dfs(src, par):
    for c in adj[src]:
        if c == par
            continue
        dfs(c, par)
        for x in range(adj[src].size):
            for y in range(adj[c].size):
                print("hello world")

The time complexity of this function is O(n^2). Why?

• Comment by Dominater069
• Trick 7 in this blog by -is-this-fft-
• Comment by Errichto
• Comment by errorgorn

Consider

for cnt in [1, n]:
    for mask in [0, 2^n]:
        if set_bit_count(mask) != cnt:
            continue
        for set bit i in mask:
            for unset bit j in mask:
                nxt = mask | (1 << j)
                dp[j][nxt] = func(dp[i][mask])

What is the time complexity of this DP? It looks like $O(n^3 \cdot 2^n)$, but it’s actually $O(n^2 \cdot 2^n)$. Why? The time complexity of the inner 2 for-loops is $O(n^2)$. Now, consider any bitmask b. How many times will the inner 2 for-loops be executed for this bitmask? Exactly once. Since there are $2^n$ unique bitmasks, the total time complexity is $O(n^2 \cdot 2^n)$.

A different argument : When cnt is equal to r, there are $n \choose r$ bitmasks for which the inner 2 for-loops would be executed. Hence, the time complexity is

$$ n^2 \cdot \left[ {n \choose 0} + {n \choose 1} + \dots {n \choose n}\right] = n^2 \cdot 2^n $$

Hence, this style can be used to solve variations of TSP and Hamiltonian path problems. Here, the transitions are intuitive, BFS like. The first level contains paths with one element, all of them are processed first. Then, the second level contains 2 elements in the path, all of them are processed before moving onto the 3rd level and so on.

But what if you want to use the classical algorithm for TSP? In this distributing DP, how are you sure that there are no partial contributions?

for mask in [0, 2^n]:
    for set bit i in mask:
        for unset bit j in mask:
            nxt = mask | (1 << j)
            dp[j][nxt] = func(dp[i][mask])

Note that any mask will take contribution from its submasks only. A submask is always less than a mask. Hence, by the time we reach a particular mask, it would already have taken all the contributions it was supposed to. Hence, its own DP value is now correct, and we can push its contribution to its supermasks.

Another argument: Arrange all the bitmasks on the number line from left to right, and draw a directed edge from x to y if x can provide contribution to y. You can see that the resulting graph would be a DAG, and 1, 2, ... n would be a toplogical ordering. Hence, processing DP from left to right works.

auto func = [](pair<int, int> small, pair<int, int> big) {
            if (small.first == big.first) {
                return small.second > big.second;
            }
            return small.first < big.first;
        };
        set<pair<int, int>, decltype(func)> current_degrees(func);