Types of Running Time:
- O(n) - Worst-case Running Time
- f(n) = O(g(n))
- Grows no faster than n
- Describes the upper bound
- It is the maximum number of steps taken in any instance of size n–calculates the maximum time an algorithm takes to complete execution.
- Formal Definition of O(n):
f(n) <= c*g(n) for all n >= n0 where n0 can be some number greater than 0 and c is some constant- Ex: f(n) = 2n + 3; g(n) = n
- 2n + 3 <= 10n, which is true
- $ \Omega $(n) - Best-case Running Time
- f(n) = $ \Omega $(g(n))
- Grows at least as fast as n
- Describes the lower bound
- Calculates the shortest time an algorithm takes to complete execution
- Formal Definition of $ \Omega $(n):
f(n) >= c*g(n) for all n >= n0 where n0 can be some number greater than 0 and c is some constant
- $ \Theta $(n) - Expected-case Running Time
- f(n) = $ \Theta $(g(n))
- Means both $ \Omega $(n) and O(n)
- Gives the average bound (expresses lower and upper bound of algorithm’s run time).
- Formal Definition of $ \Theta $(n):
c1*g(n) <= f(n) <= c2*g(n) for all n >= n0 where n0 can be some number greater than 0 and c1 and c2 are some constants
- $ \sum_{i=1}^{n} ar^{i-1} = a(\frac{1-r^n}{1-r}) $
- $ \sum_{i=m}^{n} c = c(n+1-m) $
- $ \sum_{i=m}^{n} i =\frac{n(n+1)}{2} - \frac{m(m-1)}{2} $