A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

Discussion Forum

Que. 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:
a. O(n) but not O(n^0.5)
b. O(n^0.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)^m) for some constant k > 0.5, but not O((log log n)^0.5)
Answer:O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0
Confused About the Answer? Ask for Details Here
Know Explanation? Add it Here

Similar Questions: