Tilde Notation

One way to simplify our analysis of an algorithm employing mathematical methods is to use tilde notation. Tilde notation works of the two core principles.

1. Estimate running time (or memory) as a function of input size N.
2. Ignore lower order terms.
   • When N is large, terms are negligible.
   • when N is small, we don’t care.

Example 1:	$\frac{1}{6} N^3 + 20N + 16$	~$\frac{1}{6}N^3$
Example 2:	$\frac{1}{6} N^3 + 100 N^\frac{4}{3} + 56$	~$\frac{1}{6}N^3$
Example 3:	$\frac{1}{6}N^3 + \frac{1}{2} N^2 + 1/3N$	~$\frac{1}{6}N^3$
To surmise:

• In principle: Accurate Mathematical Models are available.
• In Practice:
  • Formulas can be complicated.
  • Advanced mathematics might be required.
  • Exact models best left for the experts.

Most computer programmers will use approximate models to analyse algorithms.