### EmBeeZed's blog

By EmBeeZed, history, 5 weeks ago, ,

It turns out, that the final amortized time complexity is $O(α(n))$, where $α(n)$ is the inverse Ackermann function, which grows very slowly. In fact it grows so slowly, that it doesn't exceed $4$ for all reasonable $n$ (approximately $n<10^{600})$.

code

Question: Why this works in $O(α(n))$?

• +7

 » 5 weeks ago, # |   +6 link.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 thanks
 » 5 weeks ago, # |   +1 Read this blog to understand, atleast slightly, what exactly is going on.
•  » » 5 weeks ago, # ^ |   0 ?The linked blog doesn't even mention inverse Ackermann.
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   +12 I thought it would help him get a jist of what is exactly happening within DSU. Also, the blog does introduce a function, $log^{*}(n)$, although it doesn't mention any name. This function and how it comes up in the complexity is quite easy to see, and provides quite good bound too.
 » 5 weeks ago, # |   0 thanks
 » 5 weeks ago, # |   +50 Using path compression heuristic alone does not make your find operation work in $\mathcal{O}(\alpha(n))$. You have to use the union-by-rank heuristic as well.
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +42 Path compression alone gives amortized bound $O(\log n)$ for one operation. For all details see paper: http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p245-tarjan.pdf (see theorem 4. on page 264; the construction of the worst-case scenario starts in the middle of page 261 -- the essence is described in the last paragraph on this page and the general idea is depicted on figure 9 on page 262; also a nice summary of many variants of DSU is given in table I and II on page 280). So the whole idea is based on taking advantage of binomial tree's structure and arranging unions to construct the tree and then in such what that each iteration takes $\Theta(\log n)$.Once I wrote a task that exposes this nuance in path-compression-only DSU: You are given graph of $n$ nodes and $m$ $(1 \leq n, m \leq 4\cdot 10^6)$ weighted edges and you have compute the sum of weights of edges in the MST. Input: $n$ and $m$ in the first line. Then $m$ triples $a_i, b_i, w_i$ meaning an edge of weight $w_i$ connects vertices $a_i$ and $b_i$ where $a_i \neq b_i, 1 \leq a_i, b_i \leq n, 1 \leq w_i \leq 10^9$ and $w_1 \leq w_2 \leq \ldots \leq w_m$.The obvious solution is to use Kruskal's algorithm. Model solution using DSU with path compression and ranks:// Krzysztof Małysa // Solution in O(n + m \alpha(n)) #include #include #include #include using namespace std; vector> dsu; // (parent, rank) inline int Find(int x) noexcept { return x == dsu[x].first ? x : dsu[x].first = Find(dsu[x].first); } inline bool Union(int x, int y) noexcept { x = Find(x); y = Find(y); if (x == y) return false; if (dsu[x].second < dsu[y].second) swap(x, y); if (dsu[x].second == dsu[y].second) ++dsu[x].second; dsu[y].first = x; return true; } inline int scan_int() noexcept { int c; do { c = getchar_unlocked(); } while (c < '0' or c > '9'); int x = 0; do { x = x * 10 + (c - '0'); c = getchar_unlocked(); } while (c >= '0' and c <= '9'); return x; } int main() { int n = scan_int(); int m = scan_int(); dsu.resize(n + 1); for (int i = 1; i <= n; ++i) dsu[i].first = i; long long sum = 0; while (m--) { int a = scan_int(); int b = scan_int(); int w = scan_int(); if (Union(a, b)) sum += w; } cout << sum << '\n'; }  Solution using DSU with path compression only:// Krzysztof Małysa // Solution in O(n + m \log n) #include #include #include #include using namespace std; vector dsu; inline int Find(int x) noexcept { return x == dsu[x] ? x : dsu[x] = Find(dsu[x]); } // Unions x into y inline bool Union(int x, int y) noexcept { x = Find(x); y = Find(y); if (x == y) return false; dsu[x] = y; return true; } inline int scan_int() noexcept { int c; do { c = getchar_unlocked(); } while (c < '0' or c > '9'); int x = 0; do { x = x * 10 + (c - '0'); c = getchar_unlocked(); } while (c >= '0' and c <= '9'); return x; } int main() { int n = scan_int(); int m = scan_int(); dsu.resize(n + 1); iota(dsu.begin(), dsu.end(), 0); long long sum = 0; while (m--) { int a = scan_int(); int b = scan_int(); int w = scan_int(); if (Union(a, b)) sum += w; } cout << sum << '\n'; }  Binomal worst-case test generator for path compression only:// Krzysztof Małysa #define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,a,n) for (auto i ## __ = (n), i = (a); i <= i ## __; ++i) #define FORD(i,a,n) for (auto i ## __ = (n), i = (a); i >= i ## __; --i) #define REP(i,n) FOR(i,0, n - 1) #define ALL(h) begin(h), end(h) #define EB emplace_back #define X first #define Y second #define V vector #define tpv typedef V< typedef long long LL; typedef pair PII; tpv int> VI; tpv VI> VVI; tpv PII> VPII; tpv LL> VLL; constexpr char nl = '\n'; #define endl nl #define ris return *this #define tem template inline void mini(t& a, u&& b) { if (b < a) a = b; } tem, class u> inline void maxi(t& a, u&& b) { if (b > a) a = b; } int ceil2(int h) { return h < 2 ? 1 : 1 << (sizeof(h) * 8 - __builtin_clz(h - 1)); } tem> struct Dump { t a, b; }; tem> auto dump(t&& h) -> Dump { return {ALL(h)}; } tem> auto stub(t* h) -> decltype(cerr << *h, 0); tem> char stub(...); #define enif(o) tem> typename enable_if(0) o 1, debug&>::type operator<<(t h) #define dor > debug& operator<< struct debug { #ifdef DEBUG #define deb debug() ~debug() { cerr << nl; } enif(!=) { cerr << boolalpha << h; ris; } enif(==) { *this << '{'; for (auto a = begin(h), b = end(h); a != b;) *this << *a++ << &" "[a == b]; ris << '}'; } tem, class u dor(pair p) { ris << '(' << p.X << ", " << p.Y << ')'; } tem dor(Dump d) { *this << "{\n"; for (t a = d.a, c = a; a != d.b; ++a) *this << " " << distance(c, a) << ": " << *a << nl; ris << '}'; } #else operator int() { return 0; } tem dor(t&&) { ris; } #define deb 0 and debug() #endif }; #define imie(h...) #h ": " << (h) << " " #define LOG(h...) deb << imie(h) #define DOG(h...) deb << #h ": " << dump(h) << " " struct BinomalTree { int order; VI children; // Binomal trees of orders 0, ..., order - 1 BinomalTree(int ord = 0) : order(ord), children(ord) {} }; mt19937_64 gen__(chrono::system_clock::now().time_since_epoch().count()); LL rd(LL a, LL b) { return uniform_int_distribution(a, b)(gen__); } V G; VPII edges; int gen_binomal_tree(int order) { if (order == 0) { int id = (int)G.size(); G.EB(); return id; } int id = (int)G.size(); G.EB(order); REP (i, order) { int child = gen_binomal_tree(i); edges.EB(child, id); G[id].children[i] = child; } return id; } int transform_impl(int x, int new_node) { int k = G[x].children.back(); G[x].children.pop_back(); int o = --G[x].order; G[new_node].children[o] = x; if (o == 0) return k; return transform_impl(k, new_node); } // Simulates union(root, new node) and makes find on the deepest node which id is returned int transform(int root) { int new_node = (int)G.size(); G.EB(G[root].order); return transform_impl(root, new_node); } int main(int argc, char **argv) { ios::sync_with_stdio(false); cin.tie(nullptr); assert(argc > 1); // e.g.: ./gen 1 10 1 100 10000 0 int n, m; do { n = rd(atoi(argv[1]), atoi(argv[2])); m = rd(atoi(argv[3]), atoi(argv[4])); } while (not (n - 1 <= m and m <= n * LL(n - 1) / 2)); int max_w = atoi(argv[5]); int swap_edges = atoi(argv[6]); // In the DSU using path compression only, joining is done in one direction, but we don't know which one, so to allow generating counter-tests for both, switching this parameter between 0 and 1 changes switches the order of edge's vertices for all edges // Build binomal tree int order = 0; while ((1 << order) <= n) ++order; order = max(1, order - 4); int root = gen_binomal_tree(order); int node = root; // Add edges in the worst way for Find & Union with compression and naive linking while ((int)G.size() < n) { int new_node_id = (int)G.size(); edges.EB(node, new_node_id); node = transform(root); root = new_node_id; } // Create remaining edges set edges_set; for (auto p : edges) edges_set.emplace(min(p.X, p.Y), max(p.X, p.Y)); FOR (i, 0, m - n) { int a, b; do { do { a = rd(0, n - 1); b = rd(0, n - 1); } while (a == b); } while (not edges_set.emplace(min(a, b), max(a, b)).second); edges.emplace_back(a, b); } assert((int)G.size() == n); assert((int)edges.size() == m); VI w(m); for (int& x : w) x = rd(1, max_w); sort(ALL(w)); VI remap(n); iota(ALL(remap), 1); shuffle(ALL(remap), gen__); cout << n << ' ' << m << nl; REP (i, m) { if (swap_edges) swap(edges[i].X, edges[i].Y); cout << remap[edges[i].X] << ' ' << remap[edges[i].Y] << ' ' << w[i] << nl; } // system("grep VmPeak /proc/\$PPID/status >&2"); return 0; } 
•  » » 5 weeks ago, # ^ |   0 I prefer union-by-size. It's slightly less "correct" as a heuristic, but has the same $O$ complexity, and size is the more useful statistic for the "client" side.
•  » » » 5 weeks ago, # ^ |   +3 If I remember correctly, union by rank alone guarantees $\mathcal{O}(logN)$ performance for the find operation. The worst possible test case being that you combine sets of the same size only.
•  » » » » 5 weeks ago, # ^ |   0 According to GeeksForGeeks "using size as rank also yields worst case time complexity as $O(\log n)$" but the link to the proof is defunct and redirects to some kind of news website.
•  » » » » » 5 weeks ago, # ^ |   +3 Well, the proof for the famous "small-to-large" technique also works for explaining why the union by rank heuristic provides that time complexity. I think that the proof can be found somewhere on Codeforces. Do pardon me for my laziness to Google.
 » 5 weeks ago, # |   +1 Just a little surprised: Why did the blog post receive downvotes? I feel the above question is legitimate to ask, and it seems like it was an effective way for others to provide helpful comments / links.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +6 The solution can be googled easily.[a wiki page for it](http://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find)