Asymptotic Notations

Why use Asymptotic analysis?

Since its a well known fact that for a small input set, all algorithms perform well regardless of the complexity, so to determine the complexity we need to analyze the algorithm for large values of n , typically n -> infinity. Also we need to bound the computed value between two values(a range) , or in short create a subset within which the execution time of the algorithm falls.

An asymptote of the curve is a line such that the distance between the curve and the line approaches zero as they tend to infinity. So, we use this to determine the function which is fixed while n-> infinity.

Asymptotic notations are calculated based on if the asymptotic lower and upper bounds can be calculated for a function properly.

Various Notations

Θ — when both asymptotic upper and lower bounds can be calculated and is tight.

θ — when only asymptotic upper bound can be calculated and is tight.

Ω — when only asymptotic lower bound can be calculated and is tight.

o — when the asymptotic upper bound can be calculated but cannot be tight.

ω -Only when the asymptotic lower bound can be calculated but cannot be tight.

Θ Notation:
For functions g(n) and f(n), we define a function, Θ(g(n)) such that,
Θ(g(n)) ϵ { f(n): c1,c2,n0, all non-negative constants for, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)}

What it essentially means is that, by using the above description, we obtain a set of f(n)’s where f(n) lies between the upper and lower bounds, effectively sandwiching f(n) within c1g(n) and c2g(n).

So, we obtain a set f(n) ϵ Θ(n), for sake of convenience we use the notation, f(n) = Θ(n).

This makes, g(n) asymtotically tight bound for f(n) meaning that f(n) is equal to g(n) within a given constant factor C0.

Assumptions:

∀ f(n) ϵ Θ(n), f(n) has to be asymptotically nonnegative for sufficiently large values of n.

Also, it requires g(n) to be asymptotically nonnegative as otherwise, Θ(g(n)) = ∅

So we reach a point where, any function computed with Θ(n) has to be asymptotically nonnegative.

When computing Θ(n), lower-order terms of a function can be ignored when computing the Θ(n) as its insignificant for large values of n.
Similiarly, to compute the value of the constants c1 and c2 which define the bounds of the function, its enough if we pick a lower bound value lesser than the higher-order term and upper bound greater than the higher-order term.

For any asymptotically nonnegative function with a higher-order term 0 or if its constant we use , Θ(n0) = Θ(1). (though its sure that 1-> infinity). This notation is just used to make clarity that the function computes in constant amount of time.

θ notation:
When we have only an fixed asymptotic upper bound, we use θ(g(n)) (pronounce as big oh.)

For functions f(n) and g(n), we define a function θ(g(n)) such that,
θ(g(n)) ε {f(n), for constants , c and n0, such that 0 ≤ f(n) ≤ c.g(n) ∀ n ≥ n0}

θ(g(n)) is a subset of θ(g(n)), if it exists as Θ notation is stronger than θ notation.

-> is most commonly used as asymptotic upper bound characterizes the worst-case behavior of an algorithm.
-> we arrive at an θ notation by looking at the structure of a program

What we mean by saying a program is θ(n2) what we mean is for any value of n, above a specified n0, running time is bounded above the value of the function f(n).

Ω notation:
When we have only an fixed asymptotic lower bound, we use Ω(g(n)) (pronounced as big omega.)

For functions f(n) and g(n), we define a function Ω(g(n)) such that,
Ω(g(n)) ε {f(n), for constants, c and no, such that 0 c.g(n) ≤ f(n) for all n < n0 }

Following figure gives a clear understanding of the above notations:

Theorem 1:
For functions f(n) and g(n), f(n) ε Θ(g(n)) if and only if f(n) ε θ(g(n)) and f(n) ε Ω(g(n)).

o notation:
The asymptotic upper bound provided by \theta notation may or may not be tight. For ex, 2n ε θ(n2) is not tightly bound. In such cases we use little-oh of g(n)
For functions f(n) and g(n), we define a function o(g(n)) such that,
o(g(n)) ε {f(n), for constants c and n0, 0 ≤ f(n) ≤ c.g(n) for n>n0 and n0 a constant greater than 0}

ω notation:
When we have have an asymptotic lower bound provided by ω notation may or may not be tight.
In such case,
For functions f(n) and g(n), we define a function ω(g(n)) such that,
ω(g(n)) = { f(n), for constants, c and n0, 0 ≤ c.g(n) ≤ f(n)}