- Asymptotic notation of an algorithm is a mathematical representation of its complexity.
- Asymptotic Notations are the expressions that are used to represent the complexity of an algorithm.
Types of Asymptotic Notation:
Big - Oh Notation (O):
- Big - Oh notation is used to define the upper bound of an algorithm in terms of Time Complexity.
- That means Big - Oh notation always indicates the maximum time required by an algorithm for all input values.
- That means Big - Oh notation describes the worst case of an algorithm time complexity.
Definition:
Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) <= C g(n) for all n >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as O(g(n))
f(n) = O(g(n))
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis.
In above graph after a particular input value n0, always C g(n) is greater than f(n) which indicates the algorithm's upper bound.
Example:
We are creating array with size= 9
int a[9];
Case 1:
Suppose we want to search number 9 in the array: 9 is located at 8th index. It takes O(n) time for traversing this number.
Case 2:
Suppose we want to search 55 number in the array.
Example:
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as O(g(n)) then it must satisfy f(n) <= C g(n) for all values of C > 0 and n0>= 1
f(n) <= C g(n)
3n + 2 <= C n
f(n)=3*2+2=8
cn=4*2=8
8<=8
Above condition is always TRUE for all values of C = 4 and n >= 2.
By using Big - Oh notation we can represent the time complexity as follows....
3n + 2 = O(n)
Big - Omege Notation (Ω):
- Big - Omega notation is used to define the lower bound of an algorithm in terms of Time Complexity.
- That means Big-Omega notation always indicates the minimum time required by an algorithm for all input values.
- That means Big-Omega notation describes the best case of an algorithm time complexity.
Definition:
Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as Ω(g(n)).
f(n) = Ω(g(n))
Example:
We are creating array with size= 9
int a[9];
Case 1:
Suppose we want to search number 12 in the array: 12 is located at 0th index. It takes O(1) time for traversing this number.
Case 2:
Suppose we want to search 45 number in the array.
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis
In above graph after a particular input value n0, always C g(n) is less than f(n) which indicates the algorithm's lower bound.
Example:
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Ω(g(n)) then it must satisfy f(n) >= C g(n) for all values of C > 0 and n0>= 1
f(n) >= C g(n)
⇒3n + 2 >= C n
Above condition is always TRUE for all values of C = 1 and n >= 1.
By using Big - Omega notation we can represent the time complexity as follows....
3n + 2 = Ω(n)
Big - Theta Notation (Θ):
- Big - Theta notation is used to define the average bound of an algorithm in terms of Time Complexity.
- That means Big - Theta notation always indicates the average time required by an algorithm for all input values.
- That means Big - Theta notation describes the average case of an algorithm time complexity.
Definition:
Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1. Then we can represent f(n) as Θ(g(n)).
f(n) = Θ(g(n))
Example:
We are creating array with size= 9
int a[9];
Case 1:
Suppose we want to search number 54 in the array: 54 is located at 3rd index. O(3) is the Time complexity for searching 54.
Case 2:
Suppose we want to search 67 number in the array.
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis.
In above graph after a particular input value n0, always C1 g(n) is less than f(n) and C2 g(n) is greater than f(n) which indicates the algorithm's average bound.
Example:
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Θ(g(n)) then it must satisfy C1 g(n) <= f(n) <= C2 g(n) for all values of C1 > 0, C2 > 0 and n0>= 1
C1 g(n) <= f(n) <= C2 g(n)
⇒C1 n <= 3n + 2 <= C2 n
C1n=2
f(n)=3*2+2=8 c2(f(n))= 4*2=8
Above condition is always TRUE for all values of C1 = 1, C2 = 4 and n >= 2.
By using Big - Theta notation we can represent the time complexity as follows....
3n + 2 = Θ(n).
Analysis of Programming Constructs:
){kind=link}
0 Comments