DS Asymptotic Notations

Asymptotic Notations

Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.

  • Ο Notation

  • Ω Notation

  • θ Notation

Amortized analysis

Sometimes we find the statement in the manual that an operation takes amortized time O(f(n)). This means that the total time for n such operations is bounded asymptotically from above by a function g(n) and that f(n)=O(g(n)/n). So the amortized time is (a bound for) the average time of an operation in the worst case.

The special case of an amortized time of O(1) signifies that a sequence of n such operations takes only time O(n). One then refers to this as constant amortized time.

Such statements are often the result of an amortized analysis: Not each of the n operations takes equally much time; some of the operations are running time intensive and do a lot of “pre-work” (or also “post-work”), what, however, pays off by the fact that, as a result of the pre-work done, the remaining operations can be carried out so fast that a total time of O(g(n)) is not exceeded. So the investment in the pre-work or after-work amortizes itself.

Big 'O' Notation

The Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete.

 

Tutorialink
For a Function f(n):-
f(n)) = {g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0.}

Omega(Ω) Notation

The Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete.
 
tutorialink
for a function f(n):-
Ω(f(n)) ≥ {g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0.}

Theta(θ) Notation

The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm's running time.
 
tutorialink

for a function f(n):-
θ(f(n)) = {g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0.}

Share This Page on:


Ask Question