Register

Queries Previous Year Gate Question

630 views
0 0 votes

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

1 Answer

0 0 votes
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.
Voting & Accepting an answer helps improve the community
← Previous · Booth's coding in 8-...Next → · Ace Test Series: Com...
← Previous in category · INSERTION IN AVLNext in category → · Ace Test Series: Pro...
Position:
Show:

Related questions

1 1 vote
1 1 answer
1.2k
1.2k views
Wanted asked Jan 8, 2017
1,185 views
Programming : previous year question programming
Consider the function f defined below.struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL)|| ((p->data <= p ->n...
0 0 votes
1 1 answer
1.8k
1.8k views
Piyush Kapoor asked Sep 24, 2015
1,842 views
This is previous year Stack question but i have doubt in infix to postfix conversion .plz tell
Assume that the operators +,−,× are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^,×,+,−. The postfix expression corre...
0 0 votes
1 answers 1 answer
278
278 views
IT_021_Manish_Kumar asked Dec 6, 2025
278 views
Gate previous year 2014
If definition of complete binary tree is not given in the questions then what should by default I need to consider ?
0 0 votes
2 2 answers
349
349 views
soudipta_dutta asked Nov 4, 2025
349 views
IISc Bangalore: Entrance for Integrated PhD Previous Year Q. 1
Let $n 2$ and for $1 \leq j \leq n$, define $\mathbf{a}_j$ to be the vector in $\mathbb{R}^n$ with $j^\text{th}$ entry 0 and the remaining entries 1. Then, $\{\mathbf{a}...