## Notes Represents the upper bound, or worst-case scenario, of the runtime of an algorithm. It describes asymptotic behavior and not its exact value. The runtime is often described in relation to the size of the input or data structure. An O(n), or a linear runtime, means that the runtime increases proportionally to the size of the input. An O(n^2), or parabolic runtime, means that the runtime increases at the square of the size of the input. The same is true for any other polynomial runtime. An O(logn) means that the runtime increases at the log of the input. This also tends to be one of the best performing runtimes. An exponential runtime increases faster than any other polynomial runtime, at double the input. It is also consequently the inverse of a logarithmic runtime. This is one of the worst runtimes. A factorial runtime increases even faster than an exponential runtime and is often described by finding permutations. A constant runtime means that the runtime stays the same even if the input grows.