The recurrence relation that arises in relation with the complexity of binary search is:

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1,2,3,...,n
(ii) n,n-1,n-2,...,2,1 

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

The recurrence relation

 T(1) = 2
 T(n) = 3T(n/4)+n 

has the solution, T(n) equals to

The average number of key comparisons done on a successful sequential search in list of length n is

Which of the following is false?

(a) Consider the following algorithm. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in O-notation.

         algorithm what (n)      
             begin 
                  if n = 1 then call A 
             else begin
                   what (n-1);
                   call B(n)
             end
         end. 

(b) Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.

If T₁ = O(1), give the correct matching for the following pairs:

   (M) Tn = Tn−1 + n          (U) Tn = O(n)
   (N) Tn = Tn/2 + n          (V) Tn = O(nlogn)
   (O) Tn = Tn/2 + nlogn      (W) T = O(n2)
   (P) Tn = Tn−1 + logn       (X) Tn = O(log2n) 

If n is a power of 2, then the minimum number of multiplications needed to compute a* is

Suppose  we  want  to  arrange  the  n  numbers  stored  in any  array  such  that  all negative  values  occur  before  all  positive  ones. Minimum  number  of  exchanges required in the worst case is

Consider the following functions

Which of the following is true?

Let f(n) = n²logn and g(n) = n(logn)¹⁰ be two positive functions of n. Which of the following statements is correct?

The running time of the following algorithm

  Procedure A(n)
  If n <= 2 return(1) else return (A(⌈√n⌉)); 

is best described by:

The cube root of a natural number n is defined as the largest natural number m such that m³≤n. The complexity of computing the cube root of n (n is represented in binary notation) is:

The usual Θ(n²) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Consider the following three claims

I. (n + k)m = Θ(nm), where k and m are constants
II. 2n+1 = O(2n)
III. 22n+1 = O(2n) 

Which of these claims are correct?

where O(n) stands for order n is:

Consider the function F(n) for which the pseudo code is given below:

     Function F(n)
     begin
     F1 ← 1
     if(n=1) then F ← 3
     else For i = 1 to n do
                       begin
                       C ← 0
     For               j = 1 to F(n – 1) do
                       begin C ← C + 1 end
                       F1 = F1 * C
     end
                       F = F1
     end
     [n is a positive integer greater than zero] 

(a) Derive a recurrence relation for F(n)
(b) Solve the recurrence relation for a closed form solutions of F(n).

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with vertices and m edges has the time complexity of:

Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?

When n = 2^2k for some k ≥ 0, the recurrence relation

 T(n) = √(2)T(n/2) + √n, T(1) = 1

Arrange the following functions in increasing asymptotic order:

A. n1/3
B. en
C. n7/4
D. n log9n
E. 1.0000001n

Choose the correct alternatives (More than one may be correct). The complexity of comparison based sorting algorithms is:

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

The time complexity of the following C function is (assume n > 0)

int recursive (int n) {
   if (n == 1)
   return (1);
   else
   return (recursive (n - 1) + recursive (n - 1));
} 

Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:

counter = 0;
for (i = 1; i < = n; i++)
{ if (A[i] == 1) counter++;
      else { f(counter); counter = 0; }
}

The complexity of this program fragment is

Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M₁ × M₂ will be

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