Search code examples
javaalgorithmunionscalingunion-find

Union find: Quick find, how did the author arrive on these numbers (scaling)

In the coursera course, below union find is implemented for numbers only: https://www.coursera.org/learn/introduction-to-algorithms/lecture/EcF3P/quick-find

public class QuickFindUF
{
 private int[] id;
 public QuickFindUF(int N)
 {
 id = new int[N];
 for (int i = 0; i < N; i++)
 id[i] = i;
 }
 public boolean connected(int p, int q)
 { return id[p] == id[q]; }
 public void union(int p, int q)
 {
 int pid = id[p];
 int qid = id[q];
 for (int i = 0; i < id.length; i++)
 if (id[i] == pid) id[i] = qid;
 }
}

At the end of the slide, how are 10^9 operations per second and other 10^x numbers calculated (including 10)? All numbers are in below image: (text is also copied below)

image

Rough standard (for now).

  • 10^9 operations per second.
  • 10^9 words of main memory.
  • Touch all words in approximately 1 second.

Ex. Huge problem for quick-find.

  • 10^9 union commands on 10^9 objects.
  • Quick-find takes more than 10^18 operations.
  • 30+ years of computer time!
Solution

  • Those numbers are order-of-magnitude estimates of computer processing speed (GHz) and memory size (G "Words", i.e. ints, or 4GB).

    If you have a memory of 1 billion ints it will take you about 1 second to look at them all, so an algorithm that is O(n) on those 4 billion ints will take 1 second. If the algorithm is O(n2) it will take 1018 operations, or 1 billion seconds, approximately equal to 31 years.