Asymptotic Notation

Consider the following three functions.

f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

What is the complexity of the following code?

 sum=0;
    for(i=1;i<=n;i*=2)
         for(j=1;j<=n;j++)
            sum++;

Which of the following is not a valid string?

There are n unsorted arrays: A_1,A_2,...,A_n. Assume that n is odd. Each of A_1,A_2,...,A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case Asymptotic Notation of computing the median of the medians of A_1,A_2,...,A_n 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 ) ;
          }
     }
}

Asymptotic Notation of fun in terms of \theta notation is

Match the algorithms with their time complexities:

Consider the following functions from positive integers to real numbers:

10,\sqrt{n},n, log_{2}n,\frac{100}{n}.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the Asymptotic Notation of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls,have O(1) Asymptotic Notation. If the worst case Asymptotic Notation of this functionis O(n^{\alpha }), then the least possible value(accurate upto two decimal positions) of \alpha is .

Consider a carry lookahead adder for adding two n-bit integers,built using gates of fan-in at most two. The time to perform addition using this adder 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));
}