Queries Previous Year Gate Question

Question

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 by binary notation) is 

Can any one explain it , let n=9 =1001

and let m is 2 ,3 ,4

when m=2 0010 * 0010 * 0010 <= 1001

when m=3, 0011 * 0011 * 0011 <=1001

when m =4 , 0100 * 0100 * 0100 <=1001

How it is log n ?? Explain Plz

Answer 1

Time complexity to search using binary search is O(log n). The cube root involves to serach 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.

Comments

Where is option A , B and D