GATE 2018
October 4, 2023Mathematical-Reasoning
October 4, 2023Time-Complexity
|
Question 14
|
The cube root of a natural number n is defined as the largest natural number m such that m3≤n. The complexity of computing the cube root of n (n is represented in binary notation) is:
|
O(n) but not O(n0.5)
|
|
|
O(n0.5 but not O((log n)k) for any constant k>0
|
|
|
O((log n)k) for some constant k>0, but not O((log log n)m) for any constant m>0
|
|
|
O((log log n)k) for some constant k>0.5, but not O((log log n)0.5)
|
Question 14 Explanation:
Time complexity to search using binary search is O(log n). The cube root involves to search again O(log n) times in worst case. So time taken to find cube root is O(log2n) … (I)
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) … (II)
From (I), option A and B False
From (II), option D False.
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) … (II)
From (I), option A and B False
From (II), option D False.
Correct Answer: C
Question 14 Explanation:
Time complexity to search using binary search is O(log n). The cube root involves to search again O(log n) times in worst case. So time taken to find cube root is O(log2n) … (I)
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) … (II)
From (I), option A and B False
From (II), option D False.
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) … (II)
From (I), option A and B False
From (II), option D False.
Subscribe
Login
0 Comments