algorithm Algorithm Complexity Comparison of the asymptotic notations

Help us to keep this website almost Ad Free! It takes only 10 seconds of your time:
> Step 1: Go view our video on YouTube: EF Core Bulk Insert
> Step 2: And Like the video. BONUS: You can also share it!

Example

Let f(n) and g(n) be two functions defined on the set of the positive real numbers, c, c1, c2, n0 are positive real constants.

Notationf(n) = O(g(n))f(n) = Ω(g(n))f(n) = Θ(g(n))f(n) = o(g(n))f(n) = ω(g(n))
Formal definition∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ c g(n)∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) ≤ f(n)∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < c g(n)∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) < f(n)
Analogy between the asymptotic comparison of f, g and real numbers a, ba ≤ ba ≥ ba = ba < ba > b
Example7n + 10 = O(n^2 + n - 9)n^3 - 34 = Ω(10n^2 - 7n + 1)1/2 n^2 - 7n = Θ(n^2)5n^2 = o(n^3)7n^2 = ω(n)
Graphic interpretationO-notationΩ-notationΘ-notation

The asymptotic notations can be represented on a Venn diagram as follows: Asymptotic notations

Links

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.



Got any algorithm Question?