Algorithm Complexity || Big-Theta notation || Algorithm Pt - 2.01

Big-Theta is a tight bound that reflects both the upper and lower bounds of an algorithm's running time, unlike Big-O notation, which only shows the upper bound. A tight limit is more accurate but also more challenging to calculate.

Big-Theta is symmetric in notation: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

The expression f(x) = Ө(g(x)) can be understood intuitively to indicate that the graphs of f(x) and g(x) increase at the same pace or that the graphs "behave" similarly for large values of x.

The following is the Big-Theta notation's complete mathematical expression:Ө(f(x)) = {g: N0 -> R and c1, c2, n0 > 0, where c1 < abs(g(n) / f(n)), for every n > n0 and abs is the absolute value }

Here's one

If the If the 42n^2 + 25n + 4 operations required to complete the procedure for the input n are referred to as O(n^2), although O(n^3) and O(n^100) are other possible values. It is, however, Ө(n2) and not Ө(n3), Ө(n4), etc. Ө (f(n)) algorithms are also O(f(n)) algorithms, but

not the opposite!

Formal definition of mathematics

Ө(g(x)) is a set of functions.

Ө(g(x)) = {f(x) such that c1, c2, and N are all positive constants.0 <= c1*g(x) <= f(x)

<= c2*g(x) for all x > N}

Since g(x)  Ө(g(x)) is a set, we may say that f(x) is a member of g(x)  Ө(g(x)) by writing f(x) ∈ Ө(g(x)). The more typical approach to express the same idea is to write f(x) = Ө(g(x)) instead.

When the symbol  Ө(g(x)) occurs in a formula, we understand it to refer to an unnamed anonymous function. As in the example equationT(n) = T(n/2) + Ө(n), means T(n) = T(n/2) + f(n) where f(n) is a function in the set Ө(n).

Let f and g represent two functions that may be applied to a subset of real numbers. We createwrite f(x) = Ө(g(x)) as x->infinityIf and only if a real integer x0 and two positive constants, K and L, satisfy this condition:

K|g(x)| <= f(x) <= L|g(x)| for all x >= x0.

The term is equivalent to:

f(x) = O(g(x)) and f(x) = Ω(g(x))

A limited technique

if limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) i.e. the limit exists and it's positive, then f(x) = Ө(g(x))

Classes of Common Complexity

Name             Notation         n = 10         n = 100

Constant           Ө(1)                1                1

Logarithmic       Ө(log(n))         3                7

Linear                Ө(n)               10              100

Linearithmic      Ө(n*log(n))     30              700

Quadratic          Ө(n^2)            100            10 000

Exponential       Ө(2^n)            1 024         1.267650e+ 30

Factorial            Ө(n!)               3 628 800  9.332622e+157