We Analyze an algorithm to know that which inputs give the best result in the form of performance and which inputs give the bad result means taking more time to complete the task, and also some inputs also give average perform.
So , On the basis of Performance ,algorithm can be represent by Mathematical Expression. For representing this Mathematical Expression we use specific syntax that is called Asymptotic Analysis/Notation.
There are three types of Asymptotic Analysis:
1- Worst Case Analysis
2- Best Case Analysis
3- Average Case Analysis.
1-Worst Case
In the worst case, we calculate the upper limit of the running time of the algorithm. We must know the conditions that led to the execution of the maximum number of operations.Here maximum number of execution means lowest Rate of growth g(n) which is greater than or equal to the rate of growth f(n).
Worst case is represented by Big-O notation.
1.1 Big-O Notation :
This notation gives the tight upper bound of the given function.tight upper bound means a point from where function is regularly increasing.Big-O notation indicate the maximum time required to complete the algorithmic processing or task.
Diagrammatically Big-O notation can be represent by :
Mathematically we can represent :
f(n) =O(g(n)) means Upper bound of f(n) is g(n).
O(g(n)) defined as
O(g(n)) = {f(n) :exist positive constants c and n0 such that
0 ≤ f(n) ≤ cg(n) for all n > n0} ,
here n0 is called Threshold value for the given function.
O(g(n)) also covers all the Rate of growths which are less than g(n),means
O(n^{3}) also includes O(n^{2}) ,O(n) ,O(nlogn) and O(1) etc.
1.2 Examples on Big-O Notation
Example-1 Find upper bound for f(n) = 3n + 8
Solution: 3n + 8 ≤ 4n, for all n ≥ 8
∴ 3n + 8 = O(n) with c = 4 and n0 = 8
Example-2 Find upper bound for f(n) = n^{2} + 1
Solution: n^{2} + 1 ≤ 2n^{2}, for all n ≥ 1
∴ n^{2} + 1 = O(n^{2}) with c = 2 and n0 = 1
Example-3 Find upper bound for f(n) =n^{4} + 100n^{2} + 50
Solution: n^{4} + 100n^{2} + 50 ≤ 2n^{4}, for all n ≥ 11
∴ n^{4} + 100n^{2} + 50 = O(n^{4} ) with c = 2 and n0 = 11
Example-4 Find upper bound for f(n) = 2n^{3} – 2n^{2}
Solution: 2n^{3} – 2n^{2} ≤ 2n^{3}, for all n > 1
∴ 2n^{3} – 2n^{2} = O(n^{3} ) with c = 2 and n0 = 1
Example-5 Find upper bound for f(n) = n
Solution: n ≤ n, for all n ≥ 1
∴ n = O(n) with c = 1 and n0 = 1
Example-6 Find upper bound for f(n) = 410
Solution: 410 ≤ 410, for all n > 1
∴ 410 = O(1) with c = 1 and n0 = 1
2-Best Case
In the Best case, we calculate the lower limit of the running time of the algorithm. We must know the conditions that led to the execution of the minimum number of operations. Here minimum number of execution means largest Rate of growth g(n) which is less than or equal to the rate of growth f(n).
Best case is represented by Big-Ω notation.
2.1 Omega-Ω Notation
This notation gives the tight lower bound of the given function.tight lower bound means a point from where function is regularly decreasing.Omega-Ω notation indicate the minimum time required to complete the algorithmic processing or task.
Diagrammatically Omega-Ω notation can be represent by :
Mathematically we can represent :
f(n) =Ω(g(n)) means tight Lower bound of f(n) is g(n).
Ω(g(n)) defined as
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.
here n0 is called Threshold value for the given function.
2.2 Examples on Omega-Ω Notation
Example-1 Find lower bound for f(n) = 5n^{2}.
Solution: ∃ c, n0 Such that: 0 ≤ cn^{2}≤ 5n^{2} ⇒ cn^{2} ≤ 5n^{2} ⇒ c = 5 and n0 = 1
∴ 5n^{2} = Ω(n^{2}) with c = 5 and n0 = 1
Example-2 Prove f(n) = 100n + 5 ≠ Ω(n^{2}).
Solution: ∃ c, n0 Such that: 0 ≤ cn^{2} ≤ 100n + 5
100n + 5 ≤ 100n + 5n(∀n ≥ 1) = 105n
cn^{2} ≤ 105n ⇒ n(cn – 105) ≤ 0
Since n is positive ⇒cn – 105 ≤0 ⇒ n ≤105/c
⇒ Contradiction: n cannot be smaller than a constant
3-Average Case
Average case analysis focus on the medium performance of an algorithm,It also determines that whether the lower and upper bound of an algorithm are the same.if Worst Case (Big-O) and Best Case (Omega-Ω) are producing same output then Average Case will also be produce same results or same rate of growth.
Average case is represented by Theta-Θ notation.
3.1 Theta-Θ Notation
Notation gives the average rate of growth based on the Big-O and Omega-Ω.
if Big-O and Omega-Ω are not producing same result then Theta-Θ may not result same rate of growth, at this situation we have to consider all the possible algorithmic complexities and take average of all, the result will be average case analysis or theta-Θ notation.
Diagrammatically Theta- Θ notation can be represent by :
Mathematically we can represent :
f(n) =Θ(g(n)) means average bound of f(n) is c1g(n) and c2g(n).
Θ(g(n)) defined as
Θ(g(n)) = {f(n): there exist positive constants c1,c2 and n0
such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}.
3.2 Examples on Theta-Θ Notation
Example-1 Find Θ bound for
Solution: for all, n ≥ 2
∴ with c1 = 1/5,c2 = 1 and n0 = 2
Example-2 Prove n ≠ Θ(n^{2})
Solution: c1n^{2} ≤ n ≤ c2n^{2} ⇒ only holds for: n ≤ 1/c1
∴ n ≠ Θ(n^{2})
Example-3 Prove 6n^{3} ≠ Θ(n^{2})
Solution: c1n^{2}≤ 6n^{3} ≤ c2n^{2} ⇒ only holds for: n ≤ c2 /6
∴ 6n^{3} ≠ Θ(n^{2})
Example-4 Prove n ≠ Θ(logn)
Solution: c1logn ≤ n ≤ c2logn ⇒ c2 ≥ , ∀ n ≥ n0 – Impossible
Comparison of Asymptotic Analysis
We have discussed all types of asymptotic analysis, generally in Software Development fields ,we consider Big-O notation for code or algorithm analysis,because Big-O notation always give the tights upper bound of algorithmic function.
Omega-Ω notation (Best Case) does not have any practical importance ,if Omega-Ω and Big-O notation (Worst Case) give same rate of growth,then we choose Theta-Θ notation (Average Case) in practical.
Important Points
1- g(n) is actually a asymptotic curve in mathematics,So this analysis is called Asymptotic Analysis.
2- In this analysis , for a function f(n) we find-out the another function g(n) which provides maximum values of input(n).