Time complexity -Computer networking
Question 1 UGC NET June-2020  |
| A – A-I, B-III, C-IV, D-II |
| B – A-III, B-I, C-IV, D-II |
| C – A-III, B-I, C-II, D-IV |
| D – A-I, B-III, C-II, D-IV |
| E – None of the given options |
Show Answer With Best Explanation
Answer: E
Explanation:
Topological sort of DAG takes (V+E) time.
Bellman ford single source shortest path takes O(VE) time
Floyd Warshall’s all pair shortest path algorithm takes O(V3) time.
Kruskal’s algorithm: Sorted edges will take O(ElogV) and unsorted edges will take O(ElogE)
| Question 2 UGC NET June-2020 If algorithm A and another algorithm B take log2(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve, respectively, in one second are______ and __. |
| A – 2106 and 106 |
| B – 2106 and 1012 |
| C – 2106 and 6 x 106 |
| D – 2106 and 6 x 1012 |
Show Answer With Best Explanation
Answer : B