Consider the recurrence function

Then T(n) in terms of Θ notation is

Consider the following C function.

int fun (int n)   {
         int i, j;
         for (i = 1; i <= n; i++)   {
                for (j = 1; j < n; j += i)   {
                        printf("%d %d",i,j);
                }
          }
}

Time complexity of fun in terms of Θ notation is

The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^α), then the least possible value (accurate upto two decimal  positions) of α is _________.

An algorithm performs (log N)^1/2 find operations, N insert operations, (log N)^1/2 delete operations, and (log N)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^alog^bn). Then the value of a+10b is ________.

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

     T(n) = 2T(n/2) + Logn  

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j.  Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)).  Then the value of the product yz is _____.

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

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?

Two alternative packages A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires 10nlog₁₀n time units to process n records.What is the smallest value of k for which package B will be preferred over A?

The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?

Consider the following functions:

f (n) = 2ⁿ
g(n) = n!
h (n) = n^logn

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Consider the following C program

int f1 (int n)
{
  if(n == 0||n == 1)
    return n;
  else
    return (2*f1(n-1)+3*f1(n-2));
}
 
int f2 (int n)
{
  int i;
  int X[N], Y[N], Z[N];

  X[0]=Y[0]=Z[0]=0;
  X[1]=1; Y[1]=2; Z[1]=3;
  for(i=2; i<=n; i++) {
    X[i] = Y[i-1] + Z[i-2];
    Y[i] = 2*X[i];
    Z[i] = 3*X[i];
  }
  return X[n];
}

The running time of f1(n) and f2(n) are

Which of the following sorting algorithms has the lowest worst-case complexity?

Consider the following segment of C-code:

  int j, n;
  j = 1;
  while (j <= n)
        j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

In the following C function, let n >= m.

int gcd(n,m)
  {
     if (n%m ==0) return m;  
        n = n%m;
     return gcd(m,n);
  } 

How many recursive calls are made by this function?

What is the time complexity of the following recursive function:

int DoSomething (int n) {
    if (n <= 2)
        return 1;
    else 
        return (DoSomething (floor(sqrt(n))) + n);
}

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

Consider the following C code segment:

   int IsPrime(n)
             {
              int i,n;
              for(i=2;i<=sqrt(n);i++)
                 if(n%i == 0)
                    {printf(“Not Prime\n”); return 0;}
              return 1;
              }

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?>/p>

Consider the following C-program fragment in which i, j and n are integer variables.

 for (i = n, j = 0; i >0; i /= 2, j += i);  

Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Consider the following recurrence:

Which one of the following is true?

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

Given two arrays of numbers a₁, a₂, a₃,...a_n and b₁, b₂, .. b_n where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that a_i + a_i+1, ....a_j = b_i + b_i+1, ... b_j. or report that there is not such span,

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1

Which one of the following is FALSE?

Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)

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