DAA-Quiz1

What value does function mystery return when called with a value of 4?

  int mystery ( int number )

  {

  If ( number <= 1 )

  return 1;

  else

  return number * mystery( number – 1 );

  }

.

At most, how many comparisons are required to search a sorted vector of 1023 elements using the binary search algorithm?

The height of the shortest binary search tree of size n is .........................

1/2 n2 – 3n = O (n2).

Find the value of constant n0 if c =1, for this relation to hold, if found valid.

The running time of your program will depend upon:

1.  The algorithm, The input

2. Your implementation of the algorithm in a programming language

3. The compiler you use, The OS on your computer and Your computer hardware

4. Maybe other things: other programs on your computer

• 1 False and 2 True

• 3  False and 4 true

• All true

• All false

Give asymptotic tight bounds for the followings using master method. 

    T(n) = 9T(n/4) + n2

• n

• n2

• n2logn

• None of the above

•Give asymptotic tight bounds for the followings using master method. 

    T(n) = 9T(n/3) + 2n2 + n/3

• n2

• n2logn

• n3

• None of the above

Which sorting algorithm is faster

A.O (n log n)

B. O n^2

C. O (n+k)

 O n^3

• O(nlogn)

• O(n+k)

• O(n2)

• O(n3)

An algorithm possesses the following properties:

1.  It must be correct.

2. It must be composed of a series of concrete steps.

3. There can be no ambiguity as to which step will be performed

next.

4. It must be composed of a finite number of steps.

5.It must terminate.

Calculate the complexity using Master Theorem

T(n) = 2^nT(n/2)+n^n

• O(2^n)

• O(n^n)

• O(n!)

• None of the above