Time Complexity · #39 · 2026-05-13

What's the Big-O?

JavaScript ·Difficulty 3/3

How to play

Read the code and pick its time complexity from four Big-O choices. Think about loops, recursion, and hidden costs. Press 1–4 or click to answer.

n elements, m union/find operations total. What is the amortized time complexity?

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x)
      this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return;
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else { this.parent[rb] = ra; this.rank[ra]++; }
  }
}

Loading your progress...

Press 1 through 4, or tap a numbered choice, to answer. Back to hub