adplus-dvertising
frame-decoration

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 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: (c).O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. 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...

Similar Questions

Discover Related MCQs

Q. The following resolution rule is used in logic programming:

Derive clause (P v Q) from clauses (P v R), (Q v ¬ R)

Which of the following statements related to this rule is FALSE?

Q. Identify the correct translation into logical notation of the following assertion.

"Some boys in the class are taller than all the girls"

Note : taller(x,y) is true if x is taller than y.

Q. If a fair coin is tossed four times. What is the probability that two heads and two tails will result?

Q. The number of different n × n symmetric matrices with each element being either 0 or 1 is:
(Note: power(2, x) is same as 2x)

Q. Let A, B, C, D be n × n matrices, each with non-­zero determinant. If ABCD = 1, then B-1 is

Q. What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding?

(113. + -111.) + 7.51
113. + (-111. + 7.51)

Q. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Q. The problems 3-SAT and 2-SAT are

Q. The following propositional statement is

(P → (Q v R)) → ((P ^ Q) → R)

Q. How many solutions does the following system of linear equations have ?

-x + 5y = -1
x - y = 2
x + 3y = 3

Q. An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches -0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is:

Q. Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement ?

Q. In an M'N matrix such that all non-zero entries are covered in a rows and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

Q. Two n bit binary strings, S1 and S2, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is

Q. A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p^2 is

Q. Let G1 = (V, E1) and G2 = (V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1 ∩ G2 = (V, E1 ∩ E2) is not a connected graph, then the graph G1 U G2 = (V, E1 U E2)

Q. For the composition table of a cyclic group shown below:

* a b c d

a a b c d

b b a d c

c c d b a

d d c a b

Which one of the following choices is correct?

Q. The product of the non-zero eigenvalues of the matrix

1 0 0 0 1
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
1 0 0 0 1

is ______

Q. Which one of the following statements is TRUE about every n×n matrix with only real eigenvalues?

Q. Consider the following system of equations in three real variables x1, x2 and x3:

2x1 - x2 + 3x3 = 1
3x1- 2x2 + 5x3 = 2
-x1 + 4x2 + x3 = 3

This system of equations has