October 4, 2023
October 4, 2023
October 4, 2023
###### NIC-NIELIT STA 2020
October 4, 2023
 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:

 A O(n) but not O(n0.5) B O(n0.5 but not O((log n)k) for any constant k>0 C O((log n)k) for some constant k>0, but not O((log log n)m) for any constant m>0 D 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.
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.