Tutorial by Examples

Unlike Big-O notation, which represents only upper bound of the running time for some algorithm, Big-Theta is a tight bound; both upper and lower bound. Tight bound is more precise, but also more difficult to compute. The Big-Theta notation is symmetric: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x)) An ...

Ω-notation is used for asymptotic lower bound. Formal definition Let f(n) and g(n) be two functions defined on the set of the positive real numbers. We write f(n) = Ω(g(n)) if there are positive constants c and n0 such that: 0 ≤ c g(n) ≤ f(n) for all n ≥ n0. Notes f(n) = Ω(g(n)) means that f(n)...

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 ...