Asymptotics
Last updated
Last updated
The scaling of an algorithm refers to its behavior in terms of speed and resource consumption as the number of things it has to process increases.
We want our "interpretation" of how long an algorithm takes to be mathematical, as well as consider only the worst case.
Symbol
Use
Denotes the family of functions that grow with the order specified in the notation. Mathematically, it means that given , there are two positive constants , where .
If you think of big theta as equals, you can think of big O as less than or equal. This just means that , then for some positive integer . Usually represents the worst-case scenario.
Opposite of and represents the best case scenario. Not really used too often.
Runtime
Summation
Sum of first natural numbers 1 + 2 + 3 + 4 ... + N
Sum of first powers of 2 1 + 2 + 4 + 8 ... + N