##
ASYMPTOTIC NOTATION :
Efficiency of algorithm depends on amount of time ,storage and other resources required to execute an algorithm.
Efficiency is measured with help of asymptotic notations.
Asymptotic notations are mathematical notations used to decribe execution time of an algorithm when input tends towards a particular value or limiting value.
THREE ASYMPTOTIC NOTATIONS :
1. Big-O notation : used to measure the worst case scenerio of an algorithm .It generally gives an upper bound. in simple words we can say that (O) notation is used to measure the maximum time that an algorithm can take to execute.
2. Omega notations : used to measure the best case scenerio of an algorithm .It generally gives lower bound .In simple words we can say that theta notation is used to measure the minimum time that an alogrithm can take to execute.
3. Theta notations : used to measure the average case scenerio of an alogrithm .It generally gives the average bound. In simple words we can say that omega notation is used to measure the average time that an algorithm can take to execute.
How to find the time complexity of an algorithm with aymptotic notation?
let 'n' -> size of input
then , f(n) will represent the number of instruction executed for input value 'n'.
## Lets try to find the time complexities with asymptotic notation with help of example:
Ex 1. :
we have a main function which will execute a for loop to print hello world 'n' times. lets break the code
int n = 10; -> This instruction with execute 1-time : 1 for(int i = 0 ;i < n ;i++){ printf("hello-world"); -> This instruction will execute n-times : n }
return 0; -> This instruct will also execute 1-time : 1
f(n) = 1 + n + 1; f(n) = n + 2; the complexity of an algorithm is generally not dependent on the constants so we can ignore the '2' and therefore
the worst case complexity will be f(n) = n i.e O(n),for the above code.
Ex 2. :
Lets check another example ,this time with multiple for-loop
lets break the code
for(int i = 0 ;i <= size ;i++){ -> This instruction will execute for n times for(int j = i+1 ;j <= size - i - 1 ;j++){ ->This loop will execute for n times if(arr[j] > arr[j + 1]){ ->This instruction will execute for 1 time swap(arr[j] ,arr[j+1]); -> This instruction will execute for 1 time f(n) = n * n + 1 + 1; f(n) = n^2 + 2; we can ignore the constant value '2' ,therefore
the worst case complexity will be O(n^2)
Ex 3. :
Note : in case of worst if-else statements as well ,we will compute the complexity from if-else ,which ever block has larger complexity
in this we can see that else part has worst case complexity O(n) whereas if block will have O(1) worst case complexity
therefore we will consider the worst case complexity as O(n) for the above example
Efficiency of algorithm depends on amount of time ,storage and other resources required to execute an algorithm.
Efficiency is measured with help of asymptotic notations.
Asymptotic notations are mathematical notations used to decribe execution time of an algorithm when input tends towards a particular value or limiting value.
THREE ASYMPTOTIC NOTATIONS :
1. Big-O notation : used to measure the worst case scenerio of an algorithm .It generally gives an upper bound. in simple words we can say that (O) notation is used to measure the maximum time that an algorithm can take to execute.
2. Omega notations : used to measure the best case scenerio of an algorithm .It generally gives lower bound .In simple words we can say that theta notation is used to measure the minimum time that an alogrithm can take to execute.
3. Theta notations : used to measure the average case scenerio of an alogrithm .It generally gives the average bound. In simple words we can say that omega notation is used to measure the average time that an algorithm can take to execute.
How to find the time complexity of an algorithm with aymptotic notation?
let 'n' -> size of input
then , f(n) will represent the number of instruction executed for input value 'n'.
## Lets try to find the time complexities with asymptotic notation with help of example:
Ex 1. :
we have a main function which will execute a for loop to print hello world 'n' times. lets break the code
int n = 10; -> This instruction with execute 1-time : 1 for(int i = 0 ;i < n ;i++){ printf("hello-world"); -> This instruction will execute n-times : n }
return 0; -> This instruct will also execute 1-time : 1
f(n) = 1 + n + 1; f(n) = n + 2; the complexity of an algorithm is generally not dependent on the constants so we can ignore the '2' and therefore
the worst case complexity will be f(n) = n i.e O(n),for the above code.
Ex 2. :
Lets check another example ,this time with multiple for-loop
lets break the code
for(int i = 0 ;i <= size ;i++){ -> This instruction will execute for n times for(int j = i+1 ;j <= size - i - 1 ;j++){ ->This loop will execute for n times if(arr[j] > arr[j + 1]){ ->This instruction will execute for 1 time swap(arr[j] ,arr[j+1]); -> This instruction will execute for 1 time f(n) = n * n + 1 + 1; f(n) = n^2 + 2; we can ignore the constant value '2' ,therefore
the worst case complexity will be O(n^2)
Ex 3. :
Note : in case of worst if-else statements as well ,we will compute the complexity from if-else ,which ever block has larger complexity
in this we can see that else part has worst case complexity O(n) whereas if block will have O(1) worst case complexity
therefore we will consider the worst case complexity as O(n) for the above example