GATE CSE 2003 | Complexity Analysis and Asymptotic Notations Question 44 | Algorithms

GATE CSE 2003

MCQ (Single Correct Answer)

-0.6

The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le 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)

GATE CSE 2002

MCQ (Single Correct Answer)

-0.6

The running time of the following algorithm Procedure A(n)
If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by

O(n)

O(log n)

O(log log n)

O(1)

GATE CSE 2002

MCQ (Single Correct Answer)

-0.6

Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1. Choose an i uniformly at random fro 1..n;
2. If A[i]=x then stop else Goto 1;
Assuming that x is present A, what is the expected number of comparisons made by the algorithm before it terminates?

n-1

n/2

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Consider the following functions
$$f(n) = 3{n^{\sqrt n }}$$
$$g(n) = {2^{\sqrt n {{\log }_2}n}}$$
$$h(n) = n!$$
Which of the following is true?

h(n) is O (f(n))

h(n) is O (g(n))

g(n) is not O (f(n))

f(n) is O (g(n))

PREVIOUS NEXT