Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.
Ο Notation
Ω Notation
θ Notation
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.
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.
f(n)) = {g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0.}
Ω(f(n)) ≥ {g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0.}
θ(f(n)) = {g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0.} 
What is time space tradeoff ?Explain in brief with example.
What is time space tradeoff ?Explain in brief with example.
Ask Question