Efficiency and Orders of Growth
Mesuring base steps
use a random access machine as model of computation
- steps are executed sequentially
- step is an operation that takes constant time
- arithmetic operation
- accessing object in memory
for value of input measure time in terms of size of input
- best case: const
- worst case: linear, depends on size of list
def fact(n): # number of steps: answer = 1 # 1 (assignment) while n > 1: # 1 (comparison) <---------------+ answer *= n # 2 (assignment, + operation) | 5 * n n -= 1 # 2 (assignment, - operation) <--+ return answer # 1 for return
n (linear) <= 2 + 5 * n steps
- Given this difference in iterations through loop multiplicative factor (number of steps within loop) probably irrelevant.
- Thus, we will focus on measuring the complexity as a function of input size:
- will focus on the largest factor in this expression
- will be mostly concerned with the worst case scenario
- Need a formal way to talk about relationship between running time and size of inputs.
- Mostly interested in what happens as size of inputs gets very large, i.e. approaches infinity.
def f(x): for i in range(1000): ans = i for i in range(x): ans += 1 for i in range(x): for j in range(x): ans += 1
Overall complexity is
1000 + 2x + 2x^2.
Rules of thumb for the complexity
- Describe running time in terms of number of basic steps.
- If running time is sum of multiple terms, keep one with the largest growth rate.
- If remaining term is a product, drop any multiplicatition constans.
Use "Big O" notation (aka Omicron):
- Gives an upper bound on asymptotic growth of a function.
* O(1) denotes constant running time | * O(log*n*) denotes logarithmic running time | * O(n) denotes linear running time | * O(n * log*n*) log-linear running time | * O(n ^ c) denotes polinomial running time (c -- constant) | * O(c ^ n) denotes exponential running time \|/
- independent of inputs
- very few interesting algorithms in this class, but can often have pieces that fit this class
- can have loops or recursive calls, but number of iterations independent of size of input
- complexity grows as log of size of size of one of its inputs
- bisection search
- binary search of a list
- searching a list on order to see if an element is present
- add characters of a string assumed to be composed of decimal digits
def add_digits(s): # complexity = O(len(s)) val = 0 for c in s: val += int(c)
- complexity can depend on number of recursive calls:
def fact(n): # complexity = O(n) if n == 1: return 1 else: return n * fact(n - 1)
- many practical algorithms are log-linear
- very commonly used log-linear algorithm is merge sort
- most common polynomial algorithms are quadratic, i.e. complexity grows with square of size of input