Asymptotic-Complexity
October 26, 2023Asymptotic-Complexity
October 26, 2023Asymptotic-Complexity
| Question 23 |
An algorithm is made up of two modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order of algorithm is
| max(f(n),g(n)) | |
| min(f(n),g(n)) | |
| f(n)+g(n) | |
| f(n) * g(n) |
Question 23 Explanation:
From the given statement, algorithm consists of two modules M1 and M2.
f(n) is order of M1
g(n) is order of M2.
In order to find the order of the algorithm, there are three possible cases with f(n) and g(n)
Case-1 : if f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we can ignore this one .
Case-2 : f(n) < g(n)
In this case we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we can ignore this one.
Case-3: f(n) = g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically). So the order of the algorithm is max(f(n), g(n)).
f(n) is order of M1
g(n) is order of M2.
In order to find the order of the algorithm, there are three possible cases with f(n) and g(n)
Case-1 : if f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we can ignore this one .
Case-2 : f(n) < g(n)
In this case we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we can ignore this one.
Case-3: f(n) = g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically). So the order of the algorithm is max(f(n), g(n)).
Correct Answer: A
Question 23 Explanation:
From the given statement, algorithm consists of two modules M1 and M2.
f(n) is order of M1
g(n) is order of M2.
In order to find the order of the algorithm, there are three possible cases with f(n) and g(n)
Case-1 : if f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we can ignore this one .
Case-2 : f(n) < g(n)
In this case we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we can ignore this one.
Case-3: f(n) = g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically). So the order of the algorithm is max(f(n), g(n)).
f(n) is order of M1
g(n) is order of M2.
In order to find the order of the algorithm, there are three possible cases with f(n) and g(n)
Case-1 : if f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we can ignore this one .
Case-2 : f(n) < g(n)
In this case we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we can ignore this one.
Case-3: f(n) = g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically). So the order of the algorithm is max(f(n), g(n)).
Subscribe
Login
0 Comments