The US National Debt clock at Union Square, NYC |

That number is so big it becomes abstract and meaningless. In fact, the above picture is already from a while back. By the time you read this, the actual US National Debt is closer to $20 trillion. A number so large it becomes hard to parse, especially as the image above is missing commas.

Maybe it helps if we write down the current amount, as of writing of this text, in words and compare it with another large country:

Country | Debt in Dollars | Debt in Words/Speech |
---|---|---|

USA | $19,859,586,951,270 | Nineteen trillion, eight hundred fifty-nine billion, five hundred eighty-six million, nine hundred fifty-one thousand, two hundred seventy dollars. |

Russia | $152,205,694,374 | One hundred fifty-two billion, two hundred five million, six hundred ninety-four thousand, three hundred seventy-four dollars. |

If we actually do round off the US debt to $20 billion, the Russian debt is actually the rounding error. That's how large the US number really is.

**Payback Time**

To get a feeling for the amount, what if

*you*would spend 100% of your current net income to pay off the debt, how many years would it take you to pay off the US National Debt? For the average US citizen, it would take 525 million working years. If we combine the entire US workforce at roughly 155 million people and spend

*all*their income on relieving the US debt, it would still take an entire Trump presidency to pay off the debt. This is not realistic for a few reasons, of course.

Even if each person in the US workforce would spend a modest 10% of their net income on paying off the national debt, it would take the entire country 34 years to pay off the current debt amount, assuming the US government was able to not grow the debt even larger.

Mind-boggling numbers.

**Visualizing Large Amounts of Money**

Visualizing the debt in the shape of $100 bills may help. Here is the US National Debt in 2013, compared to an American Football field and Miss Liberty:

US National Debt visualized in stacks of $100 bills (link) |

For reference, this is what one billion dollars looks like in stacks of $100 bills:

Pictures help. Check out demonocracy.info for many other visualizations of large amounts of money.

**Short Scale and Large Scale**

The large numbers we talked about so far are huge. But, we cannot even agree on what to call really large numbers. Two different scales to talk about large numbers are in use:

**Long scale.**Every new term in the scale is one million times larger than the previous. A billion means a million millions (10^12), a trillion means a million billions (10^18), etc.**Short scale.**Every new term is one thousand times larger than the previous. A billion means a thousand millions (10^9), trillion means a thousand billions (10^12), etc.

Use of short and long scale across the world (wikipedia) |

If you care, a milliardaire and a billionaire are equally rich. Confusing.

**Algorithms and Big Numbers**

Large numbers confound us. Reasoning about large numbers is even harder. So how can we make the analysis of algorithms more insightful? Applying scales helps. Writing out large numbers in words may help. Visualization definitely helps.

Say we have a certain algorithm that we run on a modest number of 50 elements. The algorithm has implementations with different time complexity. How efficient is each algorithm? How well does it scale when we increase the number of elements? Those are questions we care about when scaling to thousands, millions, or even billions of users.

For each class of complexity, the required operations for 50 elements are at the following scale:

Those numbers may still not mean much. But, just read out the value for

**O(2^n)**. Does sound silly, right? The number for

**O(factorial)**actually sounds laughable. This is what humans do with large numbers. Our brain does not know what to do with them, gives up, and turns it into a joke. BTW. Who made up those names? Vigintillion? Novemdecilion? Undecillion?

Over their training and/or career, most software engineers have developed an intuitive feeling for complexity theory. They know that in interview questions, proposing an implementation that is

**O(n^2)**means you fell for the trap set by the interviewer. There must be a way to use a hashmap somewhere to get the cost down to

**O(n)**or even

**O(1)**.

But does the candidate really understand why

**O(n^2)**is so bad? How do

**O(n)**and

**O(n^2)**relate to each other as the number of elements grows? Let's try a visualization (click the play icon to replay):

In the interactive chart above, the number of elements are between 1 and 50 and are plotted from left to right. The vertical scale shows the number of operations, capped at 800.

**O(log n)**,

**O(n)**, and even

**O(n log n)**stay linear for a long time. The big P refers to algorithms that can be solved in polynomial time, while NP refers to nondeterministic polynomial time.

When interviewing, you definitely do not want to be nondeterministic. Already for n=10, the purple line for

**O(n^2)**is off the scale in the above chart. Search for solutions that are

**O(n)**, as is the case in linear search, or

**O(log n)**, the number of steps needed in binary search, or ideally

**O(1)**, when using a hashtable.

**Links**

- A large number of live tickers, including the current US National Debt can be found at usdebtclock.org.
- Pronouncing numbers as words makes for a nice programming interview question, but you can also go to Calculator Soup.
- Check out demonocracy.info for many other visualizations of large amounts of money.
- For more details on program analysis, check out time complexity.
- The O(x) visualization can be found amid numerous algorithm visualizations at PyAlgoViz.

## No comments:

## Post a Comment