Asymptotic-Analysis
This is a theoretical notation of algorithm analysis with a formal mathematical foundation.
Why Analyzing Algorithms?
To optimize the performance during the process from inputs to outputs. To become a better Software/Hardware developer in any fields of computer science. Improve your analytical thinking with programming abilities and many more.
A quote from The Design and Analysis of Algorithms, 1974, that:
Perhaps the most important principle for the good algorithm designer is to refuse to be content.
Upon leaving the note above, we know that constant assessments and improvements are required for the algorithm designers to advance their goals in research or work.
Note: algorithm itself is programming language-agnostic and the pseudocode is a communicative tool for algorithm's descriptive purposes.
Machine Model
Resources (memory, CPU and disk spaces) are what we take into account as analyzing the algorithms are ongoing and most of the time we care about the running time of a piece of program in a general purpose computing machine and a generalized model comes into play.
RAM (Random Access Machine) with a single core and execute one instruction a time is a proper model for analyzing algorithms. And it will bypass the hierarchy modeling of common memory/cache of real computers for analysis simplicity.
Factors of Algorithm Analysis
To devise a FAST algorithm in specific context, we should be expecting a slow growth of the worst-case running time with the input size, and it gives rise to a corresponding Big-Oh interpretation.
Worst-Case
Why do we care about worst-case scenario? 1. Worst-case running time provides an absolute uppper bound given the input size n, no even worse case could happen. 2. Worst-case often happens. For instance, a special entry of info is missing upon database querying, then query process takes the worst-case running time. 3. Average-Case usually performs as much bad as the Worst-Case: given an array with random numbers, how long it takes to determine the place of A[1..j-1] to insert A[j] into? In average, half of A[1..j-1] less than A[j] and half larger than A[j], thus the comparison time reduces by 2 but the resulting average-case running time still is a proportion of a quadratic function.
Average-Case
It is useful though rare for the average-case scenario comes into play. E.g. In situations where we require statistical, probability analysis and randomized algorithms.
Asymptotic Notations
Asymptotic analysis is a Sweet Spot for high-level reasoning about algorithms and a good enough technique to suppress details of less important Resources such as computer architecture, language spec and compiler implementations.
It is designed to focus on understanding large-scale problems for its nature in addressing a "asymptotic" alike representations. For instance, the mathematical Big-Oh notation helps describe how algorithm running time grows with input size approximating to Infinity; likewise, it could also formalize approximately how many possible connected edges there are given a fixed number of vertices of a graph structure.
Note: suppress constant factors (too system dependent) and lower-order terms (irrelevant terms for large inputs) are the best practices in analysis
Big-Oh Notation
Big-Oh Notation is the most commonly used asymptotic notations since most of the time we care about the upper bound, in other words, the worst-case of the algorithm running time.
Formal Def: Τ(n) = Ο(ƒ(n)) iff ∃ с,n0 such that Τ(n) ⩽ с ⋅ ƒ(n) for ∀ n ⩾ n0
Big-Omega Notation
Big-Omega often describes the best case running time given the algorithm but normally we care the least of it during the analysis process.
Formal Def: Τ(n) = Ω(ƒ(n)) iff ∃ с,n0 such that Τ(n) ⩾ с ⋅ ƒ(n) for ∀ n ⩾ n0
Big-Theta Notation
Big-Theta serves as a supplement to the Big-Oh for an exhaustive prediction in terms of algorithm analysis.
Formal Def: Τ(n) = Θ(ƒ(n)) iff Τ(n) = Ο(ƒ(n)) and Τ(n) = Ω(ƒ(n))
It is a common error to use Ο instead of Θ to denote the Τ(n) for specific algorithms. For instance, the MergeSort has сn ⋅ log(n) + сn operations in total. Instead of saying it bounds to Θ(n ⋅ log(n)), many would intuitively claim it bounds to Ο(n ⋅ log(n)); both statements are true but the former one is a stronger claim.
Order of Growth
There are many commonly seen order of growth functions describing the computation complexity of algorithms:
Constant: number of operations are nearly stable even if with growth of inputs processing; e.g. Ο(1), Ω(1) and Θ(1).
Linear: number of operations grows linearly with number of inputs; e.g. Ο(n), Ω(n), Θ(n).
Logarithmic: number of operations grows slowly with number of inputs; e.g. Ο(log(n)), Ω(log(n)), Θ(log(n)).
Linearithmic (combo of Linear and Logarithmic): number of operations grows faster than linear but slower than quadratic; e.g. Ο(n ⋅ log n), Ω(n ⋅ log n), Θ(n ⋅ log n).
Polynomial: running times in form of nk where k is integers.
Quadratic: number of operations grows in a power of 2 with the number of inputs; e.g. Ο(n2), Ω(n2), Θ(n2).
Cubic: number of operations grows in a power of 3 with the number of inputs; e.g. Ο(n3), Ω(n3), Θ(n3).
Exponential: number of operations grows exponentially with the number of inputs; e.g. Ο(2n), Ω(2n), Θ(2n).
Additional References
MIT Big-Oh Notation Intro, http://web.mit.edu/16.070/www/lecture/big_o.pdf
Big O versus Big Omega, https://www.programmerinterview.com/index.php/data-structures/big-o-versus-big-omega-notations/
Last updated
