Asymptotic Analysis

Single correct

• A$\log(n),\ n^{1/3},\ 2^{\log(n)},\ \log(n!)$
• B$n^{1/3},\ \log(n),\ \log(n!),\ 2^{\log(n)}$
• C$\log(n),\ n^{1/3},\ \log(n!),\ 2^{\log(n)}$
• D$2^{\log(n)},\ n^{1/3},\ \log(n),\ \log(n!)$

Single correct

• A$\Theta(n)$
• B$\Theta(\log(n))$
• C$\Theta(n\log(n))$
• D$\Theta(n^2)$

Single correct

• Aboth $O(N)$ and $\Omega(N)$
• B$O(N)$ but not $\Omega(N)$
• C$\Omega(N)$ but not $O(N)$
• Dneither $O(N)$ nor $\Omega(N)$

One or more correct

• A$f \in O(g)$
• B$f \in \Omega(g)$
• C$f \in o(g)$
• D$f \in \Theta(g)$

Answer key coming soon

Function 1                      Function 2
while n > 1 do                  for i = 1 to 100 * n do
  for i = 1 to n do               x = x + 1;
    x = x + 1;                  end for
  end for
  n = floor(n/2);
end while

One or more correct

• A$f_1(n) \in \Theta(f_2(n))$
• B$f_1(n) \in o(f_2(n))$
• C$f_1(n) \in \omega(f_2(n))$
• D$f_1(n) \in O(n)$

Answer key coming soon

Single correct

• A$f(n^2) = \theta(f(n)^2)$, when $f(n)$ is a polynomial
• B$f(n^2) = o(f(n)^2)$
• C$f(n^2) = O(f(n)^2)$, when $f(n)$ is an exponential function
• D$f(n^2) = \Omega(f(n)^2)$

Answer key coming soon

Single correct

• A$f_3, f_2, f_1$
• B$f_2, f_1, f_3$
• C$f_1, f_2, f_3$
• D$f_2, f_3, f_1$

Answer key coming soon

Single correct

• A$\Theta(n^4)$
• B$\Theta(n^2)$
• C$\Theta(n^2 \log n)$
• D$\Theta(n^3)$

Answer key coming soon

Single correct

• A$O(n)$
• B$O(n \log n)$
• C$O(n^2)$
• D$\Omega(n^2 \log n)$

unsigned long int fun(unsigned long int n){
    unsigned long int i, j = 0, sum = 0;
    for (i = n; i > 1; i = i/2) j++;
    for ( ; j > 1; j = j/2) sum++;
    return(sum);
}

Single correct

• A4
• B5
• C6
• D40

Single correct

• A$\log_2 n,\ \dfrac{100}{n},\ 10,\ \sqrt{n},\ n$
• B$\dfrac{100}{n},\ 10,\ \log_2 n,\ \sqrt{n},\ n$
• C$10,\ \dfrac{100}{n},\ \sqrt{n},\ \log_2 n,\ n$
• D$\dfrac{100}{n},\ \log_2 n,\ 10,\ \sqrt{n},\ n$

Answer key coming soon

Algorithm                                    Time complexity
(P) Towers of Hanoi with n disks             (i)   Θ(n²)
(Q) Binary search given n sorted numbers     (ii)  Θ(n log n)
(R) Heap sort given n numbers at the         (iii) Θ(2ⁿ)
    worst case
(S) Addition of two n × n matrices           (iv)  Θ(log n)

Single correct

• AP → (iii), Q → (iv), R → (i), S → (ii)
• BP → (iv), Q → (iii), R → (i), S → (ii)
• CP → (iii), Q → (iv), R → (ii), S → (i)
• DP → (iv), Q → (iii), R → (ii), S → (i)

Answer key coming soon

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);
                }
        }
}

Single correct

• A$\Theta(n\sqrt{n})$
• B$\Theta(n^2)$
• C$\Theta(n\log n)$
• D$\Theta(n^2\log n)$

Answer key coming soon

int fun1 (int n){
    int i,j,k,p,q=0;
    for (i=1; i<n; ++i) {
        p=0;
        for (j=n; j>1; j=j/2)
            ++p;
        for (k=1; k<p; k=k*2)
            ++q;
    }
    return q;
}

Single correct

• A$n^3$
• B$n(\log n)^2$
• C$n \log n$
• D$n \log(\log n)$

Single correct

• A$\Theta(n \log n)$
• B$\Theta(n)$
• C$\Theta(\log n)$
• D$\Theta(1)$

Single correct

• AOnly I
• BOnly II
• CI or III or IV but not II
• DII or III or IV but not I

Single correct

• AOnly I
• BOnly II
• CBoth I and II
• DNeither I nor II

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

Single correct

• AHalf of the product of the 3 consecutive integers.
• BOne-third of the product of the 3 consecutive integers.
• COne-sixth of the product of the 3 consecutive integers.
• DNone of the above.

int unknown(int n){
    int i, j, k=0;
    for (i=n/2; i<=n; i++)
        for (j=2; j<=n; j=j*2)
            k = k + n/2;
    return (k);
}

Single correct

• A$\Theta(n^2)$
• B$\Theta(n^2 \log n)$
• C$\Theta(n^3)$
• D$\Theta(n^3 \log n)$

Answer key coming soon

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

Single correct

• A$\Theta(n)$
• B$\Theta(n + k)$
• C$\Theta(nk)$
• D$\Theta(n^2)$

Answer key coming soon