Time efficiency is analyzed by determining the number of repetitions of the basic operation11. Typically the most time-consuming operation in the innermost loop. as a function of input size (n).
Basic Operation: The operation that contributes most towards the running time of the algorithm.
\boxed{ \text{Running Time: } T ( n ) \approx c_{op} C(n) } \\ \small \textit{where $T$ is running time,} \\ \textit{$n$ is input size,} \\ \textit{$c_{op}$ is execution time for basic operation, and} \\ \textit{$C$ is \# of times basic operation is executed} \\
Note — In short, we care about:
- How long the basic operation takes, and
- How many times we do it.
| Problem | Input Size Measure | Basic Operation |
|---|---|---|
| Searching for key in a list of n items | # of list’s items (n) | Key comparison |
| Multiplying two matrices | Matrix dimensions or total # of elements | Multiplication of two numbers |
| Checking if a given integer n is prime | n’s size = # of digits (in binary representation) | Division |
| Typical graph problem | # of vertices and/or edges | Visiting a vertex or traversing an edge |
Note — Remember: The size and format of input may impact the time efficiency of an algorithm.
Some algorithms’ efficiency depends on form of input.
\boxed{ \text{Worst Case: } C_{\text{worst}}(n) - \text{max over inputs of size $n$} } \\~\\ \boxed{ \text{Best Case: } C_{\text{best}}(n) - \text{min over inputs of size $n$} } \\~\\ \boxed{ \text{Average Case: } C_{\text{avg}}(n) - \text{avg over inputs of size $n$} }
Note — The average case is NOT the average of the worst and best case!
Q: Find the worst and best case of this sequential search algorithm.
ALGORITHM SequentialSearch(A[0..n-1],K)// Searches for given value in given array// Input: Array (A) and search key (K)// Output: Index of first element that matches K, or -1 if no matchesi \leftarrow 0while i \lt n and A[i] \ne K doi \leftarrow i \text{$+$} 1if i \lt n return ielse return -1
A:
Analysis — Time complexity is O(n) worst-case, \Omega(1) best-case, and \Theta(n) average-case. Space is O(1).
Q: Find the average case of this sequential search algorithm.
A:
In the case of a successful search, the probability of the first match occurring in the i-th position of the list is p/n for every i,
In the case of an unsuccessful search, the number of comparisons will be n with the probability of such a search being (1-p)
Thus, the total expected comparisons is simply the addition of the above two expectations:
C_{\text{avg}}(n) = \left[ 1 \times \frac{p}{n} + 2 \times \frac{p}{n} + \dots + i \times \frac{p}{n} + \dots + n \times \frac{p}{n} \right] + n (1-p)
Now, we can simplify:
\begin{aligned} C_{\text{avg}}(n) &= \frac{p}{n} [ 1 + 2 + \dots + i + \dots + n ] + n(1-p) \\ &= \frac{p}{n} \frac{n(n+1)}{2} + n(1-p) \\ &= \frac{p(n+1)}{2} + n(1-p) \end{aligned}
Therefore, the average case is:
C_\text{avg}(n) = \frac{p(n+1)}{2} + n(1-p)
Sometimes it’s better to analyze multiple runs rather than a single run.
Aside — Etymology: Amortization is from finance44. Useful for concepts like compounding APR..
- It’s about spreading the cost of the worst case over the life of the algorithm.
When inserting into a dynamic array, most inserts take O(1) time. Occasionally, the array fills up and must be doubled in size, taking O(n) time. However, because this O(n) work only happens every n insertions, the cost spreads out. The amortized cost per insertion remains O(1).
Asymptotic Analysis: Analysis of order of growth.
Definition — Asymptotic: The nature of a graph/function as it reaches large values.
- e.g., recall asymptotes from calculus, where some functions would have invisible boundaries they would get closer to, but never cross, as they approached infinity
Order of Growth: The dominant behavior of an algorithm as n \to \infty.
Why? — Looking at the asymptotic order of growth lets us compare functions by ignoring constant factors and small input sizes.
- e.g., Suppose you want to compare two array sorting algorithms. If all you analyze is how they perform on n = 5, any difference between them is negligible. It’s way more useful to see how each scales at very large n.