Commonly-used notations in the theory of Algorithms
To summarise our analysis of an algorithm there are a couple of commonly used notations to help describe our order of growth.
| notation | provides | example | shorthand for | used to |
|---|---|---|---|---|
| Big Theta | asymptotic order of growth | $Θ(N^{2})$ | $\frac{1}{2} N^{2}$ $10 N^{2}$ $5 N^{2} + 22 N log N + 3N$ | classify algorithms |
| Big Oh | $Θ(N^{2})$ and smaller | $O(N^{2})$ | $10 N^{2}$ $100 N$ $22 N log N + 3 N$ | develop upper bounds |
| Big Omega | $Θ(N^{2})$ and larger | $Ω(N^{2})$ | $\frac{1}{2} N^{2}$ $N^{5}$ $N^{3} + 22 N log N + 3 N$ | Develop Lower Bounds |
1-Sum Example
Section titled “1-Sum Example”Lets take our 1-sum problems and try to do the following:
- Establish “difficulty” of a problem
- Develop “optimal” algorithms
- Is there a Zero in the array?
- Upper Bound: Specific algorithm (example Brute Force) running time = O(N)
- Lower Bound: Examine all N Entries (any unexamined one might be 0) = Ω(N )
Optimal Algorithm: Upper bound and lower bound match therefore brute force is optimal. = Θ(N )
3-Sum Example
Section titled “3-Sum Example”Lets take our 3-sum problem and try to do the following:
- Establish “difficulty” of the problem
- Develop “optimal algorithms”
- Upper Bound: Brute-force algorithm running time is $O( N^{3} )$
- Upper bound: Improved specific Algorithm - running time is $O( N^{2}Log N)$
- Lower Bound: (Proof no other algorithm can do better) examine all N entries to solve 3-Sum. Running time of the optimal algorithm for solving 3-Sum is Ω(N ).
Open Problems
- We don’t know what the optimal algorithm for 3-Sum is as we don’t have exact upper and lower bounds