Empirical Formulas
Here are some empirical formulas that may be useful when faced with interview questions or algorithm problems. These formulas are mostly from Programming Pearls and it is recommended that the readers have a look at related content and exercises in that book.
Little's Law
Simply speaking, the law can be described as:
The average number of objects over time in a system, equals the average rate the objects leave the system minus the average time period each object stays in the system.
Expending it into a mathematical formula we can say that:
is true. This law is usually used to estimate the either one of the three parameters when knowing the other two.
Rule of 72
This rule is used to estimate an exponential growing variable's doubling time. Let's say some variable will grow by in unit time and it grows for unit time, then, when , we have the original variable's value will be nearly just doubled.
When is between and , the error of Rule of 72 won't be higher than . There are some similar rules such as Rule of 69 and so on described on Wiki.
seconds is a nano century
Yes, this formula is very simple: seconds is a nano () century. This formula is useful when estimating some program's runing time. Often it will be a bad program as the running time may be near to tens of years. You should remember to come up with a better algorithm after estimated the time.
Fermi Estimate
Fermi Estimate or Fermi Problem is an useful method to estimate the amount of something with other related assumptions and known values. The estimation usually need a dimensional analysis to check the correction. Fermi Estimate can be used to verify if some data provided by a report or advertisement is believable.
It is highly recommended by Programming Pearls that everyone should learn themselves this method and have some exercises. It will be useful in daily life.