Friday, February 12, 2016

The curse and blessing of exponential growth

Exponential growth is a common phenomena occurring all around us.  Sometimes it is good, other times not.  Simply speaking, we talk about exponential growth if some quantity is increasing as an exponential function of another quantity, i.e. y = abx.

The Good:
  1. Typically when you put your money  in the bank, your banks pays you interest as a percentage of your money, i.e. if you have \$100 in the bank and the bank pays you 5% interest a year, then you will have 1.05$\times$\$100 = \$105 after one year.  Assuming the interest rate is constant, if the next year, the bank only pays you 5% of the original \$100, then your gain will be \$5 year after year, i.e the money in the bank is 100+5n after n years.  But because of compound interest, i.e. your interest will also earn interest, you will receive 5% of \$105 = \$5.25 in interest the second year and the money in the bank will be will be \$100*1.05n after n years, i.e. an exponential growth.  If you can appreciate how fast exponential growth is, this is the best reason for anyone to save money early.
  2. In cryptography, making the number of possibilities that an encryption key can take on large is an important idea to make cryptographic techniques secure.  This is akin to choosing a long password.  The number of combinations grows exponentially with the number of digits.  For instance, a n-digit decimal number has $10^n$ possible combinations.
The not so Good:
  1. In the analysis of computer algorithms, many known algorithms for solving hard NP-complete problems (such as 3SAT) have time complexity exponential in the problem size.  This means that the size of the problem that can be solved will be limited.
  2. Many models of growth assumes an exponential growth rate, but this cannot be sustained indefinitely in a finite universe.  Some examples are Moore's Law or models of population growth.  Models of chaotic systems such as the Lorenz system and Chua's circuit also experience exponential divergence of trajectories on a small scale, but on a larger scale the trajectories remain bounded.

No comments:

Post a Comment