###### Compiler-Design

October 4, 2023###### NIC-NIELIT STA 2020

October 4, 2023# Time-Complexity

Question 14 |

The cube root of a natural number n is defined as the largest natural number m such that m^{3}≤n. The complexity of computing the cube root of n (n is represented in binary notation) is:

O(n) but not O(n ^{0.5}) | |

O(n ^{0.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(log

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.

^{2}n) … (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.

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(log

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.

^{2}n) … (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.

Subscribe

Login

0 Comments